(100分)- 单向链表中间节点（Java JS Python）

(100分)- 单向链表中间节点（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 ? len / 2 : Math.floor(len / 2); return linkedlist[mid]; }

Java算法源码

在Java中，LinkedList的get(index)方法时间复杂度为O(n)而非O(1)，这种情况下更推荐使用ArrayList来实现。

import java.util.ArrayList; import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String head = sc.next(); int n = sc.nextInt(); HashMap<String, String[]> nodes = new HashMap<>(); for (int i = 0; i < n; i++) { String addr = sc.next(); String val = sc.next(); String nextAddr = sc.next(); nodes.put(addr, new String[] {val, nextAddr}); } System.out.println(getResult(head, nodes)); } public static String getResult(String head, HashMap<String, String[]> nodes) { // LinkedList<String> link = new LinkedList<>(); ArrayList<String> link = new ArrayList<>(); String[] node = nodes.get(head); while (node != null) { String val = node[0]; String next = node[1]; link.add(val); node = nodes.get(next); } int len = link.size(); int mid = len / 2; return link.get(mid); } }

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): linkedlist = [] node = nodes.get(head) while node is not None: val, next = node linkedlist.append(val) node = nodes.get(next) length = len(linkedlist) mid = int(length / 2) return linkedlist[mid] # 算法调用 print(getResult(head, nodes))

链表结构与快慢指针解法

链表作为一种非连续存储的数据结构，本身并不具备真正的索引概念。但在实际应用中，我们经常需要访问特定位置的元素，因此大多数编程语言都为链表提供了"伪索引"功能。以Java的LinkedList为例，虽然提供了get(index)方法，但其底层实现是通过遍历链表节点（逐个访问next属性）来定位目标元素，这意味着每次索引访问都需要O(n)的时间复杂度。

在链表相关问题中，一个常见考点是如何在未知链表长度的情况下找到中间节点。这时，快慢指针算法就派上用场了。

快慢指针的工作原理是：

• 设置两个指针同时遍历链表
• 慢指针每次移动1个节点
• 快指针每次移动2个节点 当快指针到达链表末尾时，慢指针正好位于中间节点位置（对于奇数长度链表取正中间节点，偶数长度则取中间偏右的节点）。

虽然本题给出了节点数量，但这些节点可能属于不同的链表结构，因此实际链表长度仍是未知的。由于题目要求的中间节点定义与快慢指针的结果完全一致，所以采用快慢指针算法是最优解决方案。

Java算法源码

import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String head = sc.next(); int n = sc.nextInt(); HashMap<String, String[]> nodes = new HashMap<>(); for (int i = 0; i < n; i++) { String addr = sc.next(); String val = sc.next(); String nextAddr = sc.next(); nodes.put(addr, new String[] {val, nextAddr}); } System.out.println(getResult(head, nodes)); } public static String getResult(String head, HashMap<String, String[]> nodes) { String[] slow = nodes.get(head); String[] fast = nodes.get(slow[1]); while (fast != null) { slow = nodes.get(slow[1]); fast = nodes.get(fast[1]); if (fast != null) { fast = nodes.get(fast[1]); } else { break; } } return slow[0]; } }

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) { 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))