★ FEATURED ARTICLE 链表相关的算法题里找到链表的中间结点绝对是一道绕不开的入门题。不管你是刚开始刷 LeetCode、准备数据结构期末考试还是面试前临时抱佛脚这道题出现的频率都高得吓人。它的经典解法快慢指针更是后续许多链表高级技巧的基石。我最初看到这道题第一反应是“这有什么难的先数一遍长度再走一半不就完了吗”但真正动手写出来才发现链表的随机访问开销、空指针判断、偶数结点时到底返回哪一个中间结点细节多到足够让一个熟练工翻车。这篇文章就把这道题从题目含义、算法原理、代码实现到面试变体一次讲透。1. 先把题目吃透链表中间结点到底在考什么1.1 原题描述与两个示例题目内容通常是这样给定一个非空单链表的头结点 head返回链表的中间结点如果链表有两个中间结点则返回第二个中间结点。看两个例子链表 1 - 2 - 3 - 4 - 5中间结点是 3链表 1 - 2 - 3 - 4 - 5 - 6中间结点有两个分别是 3 和 4按题目要求返回 4。很多人看到这个题目觉得简单但忽略了链表的特殊性它不像数组那样可以通过下标一步跳到任意位置。数组长度是 5 时直接返回 arr[2] 就行数组长度是 6 时按题义返回 arr[3] 或 arr[2] 都可以看需求决定。链表没有随机访问能力你只能沿着 next 指针一步一步走这决定了这道题不能套用数组的惯性思维。1.2 题目里藏着的两个隐含边界题目说“非空链表”看起来不用处理 head 为 null 的情况但实际工程里健壮性要求必须判空。很多笔试环境虽然保证输入非空可面试官一追问“如果 head 为 null 呢”你如果只会写一个不带判空的函数印象分会打折扣。另一个隐含要求是“有两个中间结点时返回第二个”。这会直接左右你的实现如果面试官把要求改成“返回第一个中间结点”同样的快慢指针写法需要调整后面第五部分会细讲。这个细节非常容易被忽略但恰恰是区分“背题选手”和“理解选手”的关键点之一。2. 解法核心快慢指针的原理与复杂度分析2.1 快慢指针一张图说清核心思想设两个指针 slow 和 fast初始都指向 head。进入循环只要 fast 不是空且 fast.next 不是空就让 slow 走一步fast 走两步。当 fast 到链表末尾时slow 刚好停在中间位置。用生活场景类比你和朋友在一条笔直跑道上跑步你的速度是朋友的两倍。你跑到终点线的时候朋友虽然还差一段距离但一定处在跑道的正中间。快慢指针就是把“终点的状态”当成统一的停止信号用速度差换取位置差从而在一次遍历内定位中点。这个思想不止用在这一道题上环形链表检测、找倒数第 K 个结点本质上都是同一招。2.2 奇偶长度下slow 的落点是怎么被“自然决定”的这里需要仔细推演也是理解这道题的关键。核心循环条件通常写为while (fast fast-next) { slow slow-next; fast fast-next-next; }假设链表长度为奇数 n 5结点编号 1 到 5初始slow 1fast 1第 1 轮slow 2fast 3第 2 轮slow 3fast 5第 3 轮判断fast 已到 5fast-next 为空循环结束返回值结点 3正好是中间结点。假设链表长度为偶数 n 6结点编号 1 到 6初始slow 1fast 1第 1 轮slow 2fast 3第 2 轮slow 3fast 5第 3 轮判断fast 为 5fast-next 存在所以进入循环第 3 轮slow 4fast 先走到 NULL因为 5-next-next 已经是空第 4 轮判断fast 已是 NULL循环结束返回值结点 4也就是偶数长度时的第二个中间结点。这个结果刚好和题目要求一致。为什么叫“自然决定”因为循环多走半轮的条件由 fast-next 是否为空来控制。奇数长度时fast 最后停在最后一个有效结点fast-next 为空slow 停在中点偶数长度时fast 最后跨出链表变成 NULLslow 再往前走了一步落到了两个中点的靠右那一个。理解这个走位你就不会再纠结“为什么 slow 不是停在第一个中间结点”。2.3 循环条件为什么必须是 fast 在前、fast-next 在后写循环条件时务必先判断 fast 非空再判断 fast-next 非空。如果把条件写成while (fast-next fast)在链表长度是偶数时fast 会在某一轮结束后变为 NULL下一轮循环先判断 fast-next就会对空指针解引用程序直接崩溃。代码里“顺序”这两个字在这个场景下是真能决定生死的。另外不要用while (fast-next-next)之类的一步到位条件作为通用写法它不是完全等价在链表只有两个结点时会返回第一个结点和这道题的默认要求不符。后面讲变体时会单独说。2.4 复杂度一次遍历O(n) 时间和 O(1) 空间每次 fast 走两步slow 走一步fast 大约需要 n/2 轮走到末尾slow 也大约走了 n/2 步。于是有人会问那时间复杂度不应该是 O(n/2) 吗严格说循环最多执行约 n/2 次加上每次循环内部的常数操作总操作次数是 n 的常数倍。渐进复杂度里常数 1/2 会被吸收掉所以最终写成 O(n)。空间上只新增了两个指针变量没有使用额外数组、哈希表所以空间复杂度是 O(1)。这里尤其值得注意O(n/2) 不是一个规范的复杂度表达因为复杂度度量的是增长趋势而不是精确步数。只要记住“运行时间随链表长度线性增长”就够了。3. 代码实现三种主流语言一次写对3.1 C 版本注意指针判空顺序LeetCode 环境里的结点定义通常是struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };完整实现ListNode* middleNode(ListNode* head) { ListNode *slow head; ListNode *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } return slow; }几个容易踩的坑fast-next-next 在做解引用之前必须先保证 fast-next 不为空循环条件里的 fast-next ! nullptr 已经做了这层保护两个指针都初始指向 head不要写成 fast head-next某些变体会用这个写法但这道题里会破坏中点计算返回的是指向结点的指针不是 val也不是把整个结构体拷贝一份返回。3.2 Python 版本用 Optional[ListNode] 明确返回类型Python 写起来最接近伪代码class Solution: def middleNode(self, head: Optional[ListNode]) - Optional[ListNode]: slow head fast head while fast and fast.next: slow slow.next fast fast.next.next return slowPython 里 fast.next.next 同样必须保证 fast.next 不是 None因为 while 条件里 fast.next 的存在性已经判断过。类型标注写成 Optional[ListNode]表示可能返回空同时也兼容 head 为空的情况。LeetCode 环境默认已经导入 ListNode 和 Optional如果本地运行需要自己加from typing import Optional。这里还有一个隐藏细节while 条件依赖结点的布尔真假链表结点对象默认是 True只要不是 None 就会进入循环。所以不要把条件写成while fast.next and fast顺序会影响空指针判断。3.3 Java 版本命名规范与空指针防御Java 实现public ListNode middleNode(ListNode head) { ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow; }Java 里没有直接指针操作所有引用类型本质上都是引用所以 fast.next.next 的判空逻辑和 C 一致。写代码时一定让 fast ! null 的判断在 左侧因为 Java 的 具有短路特性如果 fast 为 null后面的 fast.next 根本不会执行从而避免 NullPointerException。我有个通用建议同一道题用三种语言各写一遍。C 能逼你关心指针生命周期Python 能帮你快速验证思路Java 则最接近大多数后端岗位的工程习惯。不同语言之间的细微差异恰好是面试官喜欢深挖的地方。4. 边界条件与常见错误这些坑我全踩过4.1 空链表和单结点链表题目虽然声明了非空但面试官喜欢追问“如果 head 是 null 怎么办”。最稳妥的做法是在函数开头加一行if (head nullptr || head-next nullptr) return head;这样逻辑自洽空链表返回空单结点链表返回它自己后续不用再特殊判断。LeetCode 里不加也完全能过因为输入保证非空加了反而显得你经验足。单结点时快慢指针的循环条件直接不满足slow 停在 head返回正确。别小看这种边界很多人在本地测试时只测长链表一提交就栽在单结点用例上。4.2 只有两个结点时返回第二个还是第一个链表只有两个结点1 - 2。按照原题题意两个中间结点分别是 1 和 2返回第二个也就是 2。用标准快慢指针初始 slow1fast1进入循环slow2fastnull退出返回 2正确。这里没有坑。但如果面试官把需求改成“返回中间靠左的结点”这就不是标准写法能直接搞定的了。判断标准就是题目说的是“第二个中间结点”还是“中间靠左的结点”一字之差代码逻辑完全不同。4.3 最容易犯的空指针崩溃我见过不少同学写下这样的错误代码while (fast-next ! nullptr fast ! nullptr) { // ... }看逻辑好像没问题但仔细想当链表长度为偶数时fast 某轮结束后变成 nullptr下一轮循环先判断 fast-next这行代码直接对空指针解引用程序立刻崩溃。正确写法必须把 fast ! nullptr 放在前面。C 和 Java 的运算符短路逻辑类似左侧为 false 时右侧不会再执行所以顺序错了就是一道必死题。还有一种错误是循环内步长写反fast fast-next; slow slow-next-next;这样 slow 会很快越界结点位置也会完全错位属于对快慢指针理解不透彻才会犯的错误。写代码前先画一遍指针走位能避开绝大多数低级问题。4.4 如果链表有环快慢指针还能用吗如果链表有环快慢指针会进入环内无限循环。原题默认输入无环但如果面试官追问“你怎么判断一个链表有环”你完全可以复用这套快慢指针如果 fast 和 slow 在某次移动后相遇说明链表有环如果 fast 先到 null说明无环。这个扩展变成了一道新题总体思路没变只是终止条件从“fast 到末尾”变成了“两指针相遇”。这也是为什么这道题被称为链表双指针第一课。5. 变体扩展从中间结点延伸到链表算法全家桶5.1 用快慢指针找倒数第 K 个结点和中间结点配套的经典题是“删除链表的倒数第 N 个结点”。思路是fast 先走 N 步然后 slow 和 fast 同步走fast 到 nullptr 时slow 刚好指向倒数第 N 个结点。和找中间结点的共同点是通过两个指针之间的相对距离把“未知目标位置”转化成“一个指针到终点时的已知条件”。理解不了快慢指针的话这两道题可以放在一起刷。5.2 用中间结点拆分链表实现链表的归并排序链表归并排序的第一步通常就是找中间结点然后从中间断开。实际代码里会这么写ListNode* slow head; ListNode* fast head; while (fast-next fast-next-next) { slow slow-next; fast fast-next-next; } ListNode* midNext slow-next; slow-next nullptr; // 切断 // 左半段 head右半段 midNext注意这里的循环条件是 fast-next fast-next-next和前文的“返回第一个中间结点”一致。因为在偶数长度链表里我们希望 slow 停在左侧中间点便于把链表切成等长的两段。如果继续用 while (fast fast-next)偶数结点时 slow 会停在下半段切分出来就不均衡了。这个细节很容易被忽略但实际工程里影响很大。5.3 链表中点判回文判断一个链表是否是回文的高效做法是先找中间结点然后反转后半段链表再和前半段逐一比较。找中间结点用的就是标准快慢指针。做完这道题等于同时复习了链表反转、中点查找、双指针遍历三个高频考点。我经常建议初学者把这三道题一起刷形成一个小闭环。5.4 面试官追问要求返回第一个中间结点怎么办如果题目改成“偶数长度时返回第一个中间结点”情况就变成了单结点返回该结点两个结点返回第一个奇数长度返回正中间。实现方式有两种。第一种是用一个 prev 指针记录 slow 的前驱循环结束后如果发现链表长度为偶数就返回 prev 而不是 slow。第二种是修改循环条件为while (fast ! nullptr fast-next ! nullptr fast-next-next ! nullptr) { slow slow-next; fast fast-next-next; } return slow;手动推演一下长度为 6 时slow 最后停在 3刚好是第一个中间结点长度为 5 时slow 停在 3也正确。这个变体虽然只改了一个条件但背后的推导过程能看出你到底是背题还是真的理解指针走位。6. 实操演练与测试用例设计6.1 构造测试链表与验证本地调试时不能只跑 LeetCode还要手动构造几个用例。我常用的最小用例集是空链表 head nullptr单结点1双结点1-2三结点1-2-3四结点1-2-3-4五结点1-2-3-4-5。奇数长度时期望返回第 3 个结点偶数长度时期望返回第 4 个结点。如果所有用例都正确再考虑更长链路。写测试用例时最好把返回结点的 val 打出来而不是只比较地址因为自定义链表地址不直观。6.2 一张表快速验证奇偶长度下的结果链表长度结点序列标准快慢指针返回位置说明111循环一次都不执行21 - 22第二个中间结点31 - 2 - 32唯一的中间结点41 - 2 - 3 - 43第二个中间结点51 - 2 - 3 - 4 - 53唯一的中间结点61 - 2 - 3 - 4 - 5 - 64第二个中间结点这张表直接回答了很多人的疑问为什么长度为 2 和 4 时返回的不是中间靠左而是中间靠右。因为题目默认“有两个中间结点时返回第二个”标准写法正好匹配这个规则。6.3 可视化走一遍六结点链表的指针轨迹还是以 1 - 2 - 3 - 4 - 5 - 6 为例初始slow 1fast 1第 1 轮slow 2fast 3第 2 轮slow 3fast 5第 3 轮slow 4fast null。画出来就是slow 每次只前进一个链表位fast 每次跨过一个结点。视觉上看fast 在第三轮后已经飞出链表尽头而 slow 停在第四个结点上。这就是“一半距离”最直观的体现。面试时如果允许在白板上画出这种指针轨迹会让你的思路非常清晰。7. 面试现场讲这道题的高级姿势7.1 先说暴力解再好到快慢指针面试官让你做这道题时不要上来就甩快慢指针。正确节奏是先口述暴力解遍历一遍求长度再从头走 length/2 步时间 O(n)空间 O(1)但要遍历两次再说明链表不能随机访问暴力解法虽然能做但不够优雅然后过渡到快慢指针一次遍历两个指针fast 到终点时 slow 正好在中点最后补充边界条件空链表、单结点、偶数长度时 fast 如何结束循环。这个由浅入深的讲法既展示了你对朴素思路的理解又突出了快慢指针的优点会明显加分。7.2 高频追问清单整理一下这个知识点常被追问的变体如果链表有环快慢指针还能找到中间结点吗不能会死循环应该先判环。如果要求返回第一个中间结点怎么改加 prev 指针或改循环条件。空间复杂度还能再低吗已经是 O(1)没有继续下降的空间。为什么不能用数组存储所有结点再取中间可以但额外空间 O(n)而且没有理解题目考察链式遍历的意图。如果链表是双向链表还需要快慢指针吗双向链表可以从两端向内逼近但题目限定单链表所以仍然要快慢指针。这些追问覆盖了链表这个知识面里大部分常见考核方向弄懂了它们比只背答案强得多。7.3 易错点自查清单写代码前在心里默念几件事循环条件先判 fast再判 fast.next循环体内先移动 slow 还是先移动 fast顺序不影响正确性但逻辑要一致返回的是 slow 结点本身不是 slow-val不要修改输入链表的结构如果题目要求返回第一个中间结点不要直接用标准快慢指针。8. 写在最后一点刷题建议这道题我在面试中见过也在带新人时出过。我个人的体会是不要急着背代码先手动画链表推演五遍。我第一次写的时候就犯过 fast 判空顺序错误也试过把 fast-next-next 放在判断条件里导致崩溃。如果你能把奇数、偶数、两个结点、单结点这四种情况都推演明白这道题就算彻底掌握了。后续刷题时链表类题目可以成套安排环形链表、删除倒数第 N 个结点、回文链表、合并两个有序链表。这套组合拳练完你会发现自己对链表操作的肌肉记忆已经形成了。面试前再花十分钟把快慢指针的走位在纸上画一遍比临时翻代码有用得多。
阅读完成 · 觉得有帮助？
