华为OD机试 – 单向链表中间节点（Java & JS & Python）

题目描述

求单向链表中间的节点值，如果奇数个节点取中间，偶数个取偏右边的那个值。

输入描述

第一行 链表头节点地址 后续输入的节点数n

后续输入每行表示一个节点，格式 节点地址 节点值 下一个节点地址(-1表示空指针)

输入保证链表不会出现环，并且可能存在一些节点不属于链表。

输出描述

单向链表中间的节点值

用例

题目解析

用例1示意图如下

JS本题可以利用数组模拟链表

基于链表数据结构解题

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */const readline = require("readline");const rl = readline.createInterface({  input: process.stdin,  output: process.stdout,});const lines = [];let head;let n;rl.on("line", (line) => {  lines.push(line);  if (lines.length === 1) {    [head, n] = lines[0].split(" ");  }  if (n && lines.length === n - 0 + 1) {    lines.shift();    const nodes = {};    lines.forEach((line) => {      const [addr, val, nextAddr] = line.split(" ");      nodes[addr] = [val, nextAddr];    });    console.log(getResult(head, nodes));    lines.length = 0;  }});function getResult(head, nodes) {  const linkedlist = [];  let node = nodes[head];  while (node) {    const [val, next] = node;    linkedlist.push(val);    node = nodes[next];  }  const len = linkedlist.length;  const mid = len % 2 === 0 " /> {      const [addr, val, nextAddr] = line.split(" ");      nodes[addr] = [val, nextAddr];    });    console.log(getResult(head, nodes));    lines.length = 0;  }});function getResult(head, nodes) {  let slow = nodes[head];  let fast = nodes[slow[1]];  while (fast) {    slow = nodes[slow[1]];    fast = nodes[fast[1]];    if (fast) {      fast = nodes[fast[1]];    } else {      break;    }  }  return slow[0];}

Python算法源码

# 输入获取head, n = input().split()nodes = {}for i in range(int(n)):    addr, val, nextAddr = input().split()    nodes[addr] = [val, nextAddr]# 算法入口def getResult(head, nodes):    slow = nodes.get(head)    fast = nodes.get(slow[1])    while fast is not None:        slow = nodes.get(slow[1])        fast = nodes.get(fast[1])        if fast is None:            break        else:            fast = nodes.get(fast[1])    return slow[0]# 算法调用print(getResult(head, nodes))