页面加载中…
P3900. 寻找链表的中间节点
简单通过率 74% · 提交 308 · 通过 227
100分数组双指针2025A链表哈希表
本题改编自华为 OD 机考真题方向 · 考点：100分 / 数组 · 难度：简单
小慕在项目中维护了一个L，现在需要编写程序输出L保存的数据。 如果有两个中间节点，则输出第二个中间节点保存的数据。 例如： 给定L为1→7→5，则输出应该为7； 给定L为1→2→3→4，则输出应该为3。
这类题属于华为 OD 机考真题方向中「100分 / 数组」方向的高频题型，通常考察对「100分 / 数组」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。
提示：带虚线的词点一下有通俗解释。
输入描述
每个输入包含1个测试用例。每个测试用例第一行给出链表首节点的地址、节点总个数为正整数N (N≤105）。
节点的地址是5位非负整数，NULL地址用-1表示。
接下来有N行，每行格式为：
Address Data Next
其中Adress是节点地址，Data是该节点保存的 整数数据，Next是下一个节点的地址。
输出描述
对每个测试用例，在一行中输出L中间节点保存的数据。
如果有两个中间节点，则输出第二个中间节点保存的数据。
补充说明：
以确保输入的节点所构成的链表L不会成环，但会存在部分输入节点不属于链表L的情况
示例
示例 1
输入示例
00100 4 00000 4 -1 00100 1 12309 33218 3 00000 12309 2 33218
输出示例
3
说明：
链表为 1->2->3->4，中间节点为3
示例 2
输入示例
10000 3 76892 7 12309 12309 5 -1 10000 1 76892
输出示例
7
说明：
链表为 1->7->5，中间节点为7
时间限制 1000 ms · 内存限制 128 MB
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。
相关图解步骤
把本题套路迁移到 LeetCode 动画里看
先看指定步骤补关键知识点，再回到本题完成标准输入输出。
解题思路
本题是一道经典的链表题，链表的中间节点。 可见 2024/07/06 真题讲解（链表 + 双指针专题） 中的对应视频讲解。
邻接表储存链表
本题不同于常规使用节点类 ListNode 来储存链表，而是直接给出了链表每一个节点的 节点地址、数据、下一个节点，我们可以转化为我们熟悉的 邻接表 来储存所有节点。将所有节点数据储存在哈希表 linked_list_dic 中的代码如下：
链表节点的前进
我们可以把链表看作是一个 只有一条路径的有向图。已知当前节点为 cur_node，如果我们要获得下一个节点 nxt_node，可以使用 nxt_node = linked_list_dic[cur_node][1] 来获得。如果要让 cur_node 前进到 nxt_node 的位置，我们仅需要以下代码即可完成：
解法一：用列表储存所有链表节点数据
对于本题而言，一种最直接的做法就是 直接遍历整条链表，并用一个新的列表 nums 储存链表中所有节点的数据，最后取出 nums 中索引为 len(nums)//2 的数据即为所需要的 中间节点的值。
解法二：快慢双指针
另一种更加高效的解法是利用 双指针。设置 slow 和 fast 快慢两个双指针，均从链表头节点 head 出发。前进规律为：
fast向前走两步slow向前走一步
当 fast 走到链表的尾部时，slow 对应的恰好是链表的 中间节点，输出对应的值即可。
这种方法的优点是 只需要使用 `slow` 和 `fast` 两个指针，无需使用额外的 nums 列表来储存所有节点的值，空间复杂度更低。
代码
解法一（数组解法）
我的提交
登录后可查看你在本题的历史提交，以及每次的各用例通过情况。
