【华为OD-E卷-寻找链表的中间结点 100分（python、java、c++、js、c）】
题目
给定一个单链表 L，请编写程序输出 L 中间结点保存的数据。
如果有两个中间结点，则输出第二个中间结点保存的数据。例如：
给定 L 为 1→7→5，则输出应该为7； 给定 L 为 1→2→3→4，则输出应该为3；
输入描述
- 每个输入包含1个测试用例。
每个测试用例：
第一行给出链表首结点的地址、结点总个数正整数 N （≤ 10^5）。结点的地址是5位非负整数，NULL地址用-1表示。
接下来有N行，每行格式位：
Address Data Next
其中Address是结点地址，Data是该结点保存的整数数据（0 ≤ Data ≤ 10^8），Next是下一结点的地址。
输出描述
- 对每个测试用例，在一行中输出 L 中间结点保存的数据。 如果有两个中间结点，则输出第二个中间结点保存的数据。
备注
已确保输入的结点所构成的链表 L 不会成环，但会存在部分输入结点不属于链表 L 情况 。
用例
用例一：
输入：
00010 4
00000 3 -1
00010 5 12309
11451 6 00000
12309 7 11451
输出：
6
用例二：
输入：
10000 3
76892 7 12309
12309 5 -1
10000 1 76892
输出：
7
python解法
- 解题思路：
这道题目要求我们在一个链表中找到中间节点的值。输入提供了链表节点的地址、数据以及下一个节点的地址，我们需要通过给定的节点关系来构建链表，并通过快慢指针方法来找到链表的中间节点。
步骤：
输入解析：
读取链表的头节点地址 first 和节点的数量 num。
使用哈希表（字典）来存储链表中的每个节点，节点的键是地址，值是节点对象，节点对象包含数据 val 和下一个节点的地址 next。
构建链表：
遍历所有节点的描述信息，使用哈希表存储每个节点的地址及其对应的值和下一个节点的地址。
使用快慢指针法找到中间节点：
初始化快指针 fast 和慢指针 slow 都指向链表的头节点。
快指针每次走两步，慢指针每次走一步。当快指针到达链表的末尾时，慢指针刚好指向中间节点。
如果链表节点个数为偶数，慢指针最终会指向第二个中间节点。
输出中间节点的值。
# 链表节点定义
class ListNode:
def __init__(self, val, next_node):
self.val = val # 节点的值
self.next = next_node # 指向下一个节点的地址
# 主函数：查找链表的中间节点
def find_middle_node():
# 字典存储所有节点，键为节点地址，值为节点对象
nodes = {}
# 读取输入：链表头节点的地址和链表节点数量
first, num = input().split()
n = int(num)
# 读取链表的每个节点信息
for _ in range(n):
addr, data, next_addr = input().split()
# 将节点地址映射到 ListNode 对象
nodes[addr] = ListNode(int(data), next_addr)
# 初始化快慢指针
slow = first # 慢指针从头节点开始
fast = first # 快指针从头节点开始
# 遍历链表，使用快慢指针法找到中间节点
while fast != "-1" and nodes[fast].next != "-1":
slow = nodes[slow].next # 慢指针走一步
fast = nodes[nodes[fast].next].next # 快指针走两步
# 输出慢指针所在节点的值，即中间节点的值
print(nodes[slow].val)
# 调用函数，查找并打印链表的中间节点
find_middle_node()
java解法
- 解题思路
- 这段代码实现的是链表的环检测问题，具体来说，给定一个链表的起始节点及其后续节点信息，我们需要判断链表是否存在环，并输出环的入口节点的值。
问题背景：
给定一个链表，每个节点包含两个信息：
节点的值。
下一个节点的标识符（或标记为 -1，表示链表结束）。
输入数据包含链表的起始节点、节点数目及每个节点的详细信息。
需要找出链表中的环的入口节点，如果存在环。
思路：
使用哈希表存储节点信息：我们使用一个 Map 来保存每个节点的值和指向下一个节点的标识符。
快慢指针法：
使用两个指针 slow 和 fast，slow 每次移动一步，fast 每次移动两步。
如果链表存在环，两个指针最终会相遇。
在快慢指针相遇后，重新设置一个指针从起始节点开始，每次一步一步前进，另一个指针不动，最终会在环的入口节点相遇。
输出环的入口节点的值。
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {
// 定义链表节点类
public static class Node {
int val; // 节点的值
String next; // 指向下一个节点的标识符
// 构造函数初始化节点
public Node(int val, String next) {
this.val = val;
this.next = next;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Map<String, Node> map = new HashMap<>(); // 用哈希表存储每个节点的信息
// 读取输入的起始节点和节点数目
String[] input = sc.nextLine().split(" ");
String start = input[0]; // 起始节点
int n = Integer.parseInt(input[1]); // 节点数目
// 读取每个节点的信息，填充到哈希表中
for (int i = 0; i < n; i++) {
String[] nodeInfo = sc.nextLine().split(" ");
map.put(nodeInfo[0], new Node(Integer.parseInt(nodeInfo[1]), nodeInfo[2]));
}
// 初始化快慢指针，初始位置均为起始节点
String slow = start, fast = start;
// 快慢指针法：快指针每次走两步，慢指针每次走一步
// 如果有环，快指针和慢指针一定会相遇
while (!fast.equals("-1") && !map.get(fast).next.equals("-1")) {
slow = map.get(slow).next; // 慢指针走一步
fast = map.get(map.get(fast).next).next; // 快指针走两步
}
// 输出慢指针所在节点的值，作为环的入口节点的值
System.out.println(map.get(slow).val);
}
}
C++解法
- 解题思路
- 这段代码解决的问题是 链表的环检测，并找到环的入口节点，通过使用 快慢指针法 来实现。
具体思路如下：
链表的表示：
每个节点包含 data（节点的值）和 next（指向下一个节点的地址或 -1，表示链表结束）。
使用哈希表（unordered_map）存储链表中每个节点的地址和节点数据。
环检测和寻找环的入口节点：
使用 快慢指针（slow 和 fast），其中 slow 每次走一步，fast 每次走两步。
如果链表中存在环，slow 和 fast 指针最终会相遇。
在相遇之后，重新设置一个指针从链表的起始节点开始，每次一步一步前进，另一个指针不动，最终会在环的入口处相遇。
输出环的入口节点的值。
主要步骤：
读取输入，构建链表。
使用快慢指针检测环并找到入口节点。
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
// 链表节点结构体
struct Node {
int data; // 节点的值
string next; // 下一节点的地址（字符串）
// 默认构造函数
Node() : data(0), next("") {}
// 带参数的构造函数
Node(int data, const string& next) : data(data), next(next) {}
};
// 查找环的入口节点
void find_middle_node() {
unordered_map<string, Node> nodes; // 哈希表，用于存储每个节点
string first; // 链表的起始节点地址
int n; // 节点的数量
// 读取起始节点地址和节点数量
cin >> first >> n;
cin.ignore(); // 忽略行尾的换行符
// 读取每个节点的信息并存入哈希表
for (int i = 0; i < n; ++i) {
string addr, next_addr; // 当前节点地址和下一节点的地址
int data; // 当前节点的值
cin >> addr >> data >> next_addr;
nodes[addr] = Node(data, next_addr); // 将节点信息存入哈希表
}
// 快慢指针初始化，分别从起始节点开始
string slow = first, fast = first;
// 快慢指针法：快指针每次走两步，慢指针每次走一步
// 如果有环，快指针和慢指针最终会相遇
while (fast != "-1" && nodes[fast].next != "-1") {
slow = nodes[slow].next; // 慢指针走一步
fast = nodes[nodes[fast].next].next; // 快指针走两步
}
// 输出慢指针所在的节点数据，作为环的入口节点
cout << nodes[slow].data << endl;
}
// 主函数，执行链表环入口查找
int main() {
find_middle_node(); // 调用函数查找环的入口节点
return 0;
}
C解法
更新中
JS解法
节点的地址。
节点的值。
指向下一个节点的地址，若指向 -1 表示链表结束。
我们可以通过以下步骤来解决问题：
构建链表：使用一个哈希映射（Map）存储每个节点的地址和节点对象。每个节点对象包含节点的值和指向下一个节点的地址。
遍历链表：从给定的起始节点开始，按照链表的连接关系遍历链表，将节点按顺序存入数组。
找中间节点：找到链表的中间节点。可以通过计算链表长度的一半索引来获得中间节点，并返回它的值。
// 定义链表节点类
class Node {
constructor(data, next) {
this.data = data; // 节点的值
this.next = next; // 指向下一个节点的地址
}
}
// 查找链表的中间节点
function findMiddleNode(start, nodes) {
let list = []; // 用于存储链表节点的数组
let current = start; // 从起始节点开始遍历
// 遍历链表，直到找到终点 '-1'
while (current !== '-1') {
const node = nodes.get(current); // 获取当前节点
list.push(node); // 将节点添加到数组中
current = node.next; // 更新当前节点为下一个节点
}
// 返回中间节点的值
return list[Math.floor(list.length / 2)].data;
}
// 示例用法：读取输入并执行操作
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
// 读取第一行，获取链表的起始节点和节点数量
rl.question('', (firstLine) => {
const [start, count] = firstLine.split(" "); // 获取起始节点地址和节点数量
const nodes = new Map(); // 创建一个哈希映射存储所有节点
let linesRead = 0; // 记录已经读取的节点数量
// 监听每一行输入
rl.on('line', (line) => {
const [address, data, next] = line.split(" "); // 解析每个节点的地址、值和下一个地址
nodes.set(address, new Node(parseInt(data), next)); // 将节点存入哈希映射
linesRead++; // 更新已读取的节点数量
// 当读取的节点数等于总节点数时，输出中间节点的值
if (linesRead === parseInt(count)) {
console.log(findMiddleNode(start, nodes)); // 找到中间节点并输出
rl.close(); // 关闭输入流
}
});
});
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏