1. 第876题被放进Hot 100不是因为它难而是因为它底盘1.1 题目只要一句话但信息量并不小Hot 100刷题路线走到第20题我把它留给了一道看起来一分钟就能写完的题链表的中间结点。LeetCode 876放在Hot 100里其实挺有迷惑性——代码短、解法固定、不涉及复杂推导很多人扫一眼就觉得背个模板就行。但真到了面试这道题反而是翻车重灾区。题目原文很简洁给定单链表的头节点 head返回链表的中间节点如果链表有两个中间节点则返回第二个中间节点。注意这句如果有两个中间节点则返回第二个。这是整道题最容易被忽略、也最决定代码形态的一句话。链表长度是偶数时比如 1-2-3-4中间节点到底算节点2还是节点3题目明确告诉你返回节点3。这个约定直接影响了快慢指针的初始化和终止条件后面我会专门展开。为什么这样一道看起来像送分题的题目能进Hot 100我的理解是它考的不是你会不会找中点而是你对链表遍历、指针移动、边界条件这三件事的整体掌控力。链表中点在算法面试里属于地基型操作后面刷回文链表、重排链表、环形链表全都要用到它。地基打不牢后面每一道题都会给你颜色看。1.2 中间节点的约定为什么题目要强调第二个我们先捋清楚中间节点这个概念在链表里到底怎么定义。长度为奇数1-2-3-4-5中间节点明显是节点3没有歧义。长度为偶数1-2-3-4数学上可以说中间有两个节点节点2和节点3。LeetCode 876选择了后者也就是靠右的那一个。如果用0-based索引来表示长度为n的链表中间节点对应的下标就是 n // 2。这个公式很重要后面两遍遍历的写法会直接用上。我在刷题时有个习惯拿到这种有明确约定的题目会先把约定写在题解笔记最上面。比如这一题我会写偶数长度返回靠右节点等价于索引 n//2。这看起来是废话但它决定了你选择哪种双指针写法。很多教程里教的双指针是慢指针指向头、快指针指向第二个节点那种写法找到的是靠左的中间节点。LeetCode 876要的是靠右的所以你必须用另一套写法。如果面试时遇到一道找中间节点的题但没说偶数情况我建议先反问面试官一句如果链表长度是偶数您希望返回前一个还是后一个这一问能直接展现出你对边界条件的敏感度比闷头写代码加分得多。2. 两遍遍历面试初期最稳的保底写法2.1 第一遍数长度第二遍走一半很多人一上来就写快慢指针我不反对但我觉得更稳妥的起点是先掌握两遍遍历。思路非常简单第一遍从头走到尾数出链表长度 n第二遍从头开始走 n/2 步整数除法停下来的节点就是答案。对应到本题因为要返回靠右的中间节点所以走 n // 2 步是对的。比如 n5n//22从头节点开始走两步到达节点3n6n//23走三步到达节点4。这和上一节说的中间节点下标是 n//2完全吻合。Python参考实现是这样class Solution: def middleNode(self, head: Optional[ListNode]) - Optional[ListNode]: length 0 cur head while cur: length 1 cur cur.next mid_steps length // 2 cur head for _ in range(mid_steps): cur cur.next return cur这段代码的时间复杂度是 O(n)空间复杂度 O(1)。实际提交完全能过代码也很好理解。我在带新人刷题的时候会要求他们先把这种写法写顺——因为两遍遍历背后是先获取全局信息、再定位的通用思维很多链表题目都依赖这种思路。2.2 一个容易把自己绕晕的细节步数到底怎么算两遍遍历最常见的翻车点不是循环写错而是步数和节点编号混在一起。有初学者会这样想5个节点的链表中间是第3个节点所以从头部移动 3 步。这是错的。头节点本身已经是第1个节点想走到第3个节点只需要移动 2 步。而 n//2 恰好就是 2不需要额外加1。我见过有人写 mid (length 1) // 2 然后循环 mid 次结果长度是5的时候移动3步跑到了节点4。这就是没搞清楚移动步数和节点序号的区别。我自己的记忆方法是移动步数永远等于目标节点的0-based下标。中间节点下标是 n//2那就移动 n//2 步没有任何例外。长度是偶数6下标是3移动3步到节点4长度是奇数5下标是2移动2步到节点3。用一个公式全解决了。2.3 用数组缓存节点这个解法要慎用还有一种很偷懒的写法遍历链表时把所有节点放进一个数组然后直接返回数组下标 n//2 的元素。class Solution: def middleNode(self, head: Optional[ListNode]) - Optional[ListNode]: nodes [] cur head while cur: nodes.append(cur) cur cur.next return nodes[len(nodes) // 2]功能上完全正确LeetCode提交也能过思路还特别直白。但我不建议在正式面试中用这个作为主答案因为它把链表问题变成了数组问题。你相当于把链表的节点指针都缓存起来了然后用数组的随机访问能力直接取中间。面试官想考察的是你对链表只能逐节点访问这个特性的理解你用数组绕过了这个考察点。如果面试官追问为什么不用下标访问你当然可以说链表本身不支持随机访问所以借助数组缓存。但更好的策略是先给两遍遍历或快慢指针再把数组缓存作为一个额外思路提一下而不是把它当主解。3. 快慢指针用两步对一步的时间差把中点套出来3.1 快慢指针的几何直觉龟兔赛跑快慢指针是这个问题的经典最优解没有之一。它的直觉可以用一个生活场景解释两个人同向跑步甲的速度是乙的两倍。甲跑到终点的时候乙一定刚好在跑道的一半位置。我们不需要知道跑道总长只需要让两个人同时出发速度差两倍就能在甲到达终点时抓住乙的位置——而这个位置就是中点。放到链表里就是慢指针 slow 每回合移动一个节点快指针 fast 每回合移动两个节点。快指针到链表末尾时慢指针恰好停在中间。这里有个很关键的恰好如果链表长度是奇数快指针会停在最后一个节点上slow 落在正中间如果长度是偶数快指针会越过链表末尾变成 nullslow 落在靠右的那个中间节点上。LeetCode 876要的正好是靠右的节点所以这个算法天然契合题目约定。3.2 while fast and fast.next 是唯一的理想终止条件快慢指针的代码框架是这样的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 slow核心就在 while 那一行fast 和 fast.next 必须同时判空。为什么两个条件缺一不可我们来推演一下奇数长度链表比如 1-2-3-4-5。移动过程fast 先是节点3然后节点5当 fast 停在节点5时fast.next 是 null。此时 while 条件 fast.next 为假循环退出slow 停在节点3。偶数长度链表比如 1-2-3-4-6这里我说6个节点1-2-3-4-5-6。移动过程fast 先是节点3然后节点5接着越界变成 null。此时 while 条件 fast 为假循环退出slow 停在节点4。所以奇数看 fast.next 是否为空偶数看 fast 是否为空。你必须在条件里同时判断这两个才能让两种长度都能正确退出。少写一个要么空指针异常要么循环退出时机不对。Java 版本特别注意判空顺序class Solution { public ListNode middleNode(ListNode head) { ListNode slow head, fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; } return slow; } }Java的 有短路机制先判断 fast ! null如果 fast 已经为 null 就不会再去访问 fast.next也就不会抛空指针。所以顺序不能反过来写不能先写 fast.next ! null fast ! null否则一旦 fast 为 null 就直接报错。C版本也是一个套路class Solution { public: 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; } };3.3 一个非常隐蔽的笔误让 fast 先走一步很多链表技巧教程里有另一种双指针写法叫快指针先指向第二个节点slow head fast head.next while fast and fast.next: slow slow.next fast fast.next.next return slow这套写法找的是靠左的中间节点不是LeetCode 876要的靠右节点。我们来验证一下长度21-2。初始 fast 在节点2fast.next 为 null循环不执行slow 停在节点1。但题目期望返回节点2。长度41-2-3-4。初始 fast 在节点2进入循环一次后 slow 到节点2、fast 到节点4下一轮 fast.next 为 null退出slow 停在节点2。但题目期望返回节点3。同样的代码只是 fast 初始位置差了一个节点结果就从靠右中间节点变成了靠左中间节点。这就是为什么我反复强调这一题必须让 slow 和 fast 同时从 head 出发。如果面试时你用的是 fast head.next 这个初始化然后面试官给了一个偶数长度的例子当场就会暴露。所以请把同时从 head 出发这句话刻在脑子里。3.4 复杂度与空间优势快慢指针的时间复杂度是 O(n)因为 fast 每轮移动两个节点整体遍历次数大约 n/2仍然是线性级别。空间复杂度 O(1)只用了两个指针变量没有额外数组没有递归栈。这正是面试官期待看到的标准答案。相比两遍遍历它最大的优势是一遍遍历解决问题——fast 在前面探路slow 在后面记录等 fast 到达终点时答案已经攥在手里。这种用时间差代替第二遍扫描的思路是双指针技术的核心价值也是后面很多难题的出发点。4. 边界值设计与自测用例比主逻辑更容易被扣分的地方4.1 空链表与单节点链表LeetCode 876的题目约束里链表长度在 [1, 100] 之间所以空链表不会出现在评测用例里。但我在面试中仍然习惯性处理它因为很多面试官会追问如果 head 是 null 呢快慢指针的空链表行为其实很安全slow 和 fast 都指向 nullwhile 条件 fast and fast.next 直接短路返回 null。这就是我们想要的结果不需要额外加 if。这是这个解法的一个隐藏优点——边界情况被循环条件天然兜住了。单节点链表 1-null 的情况fast 节点1fast.next nullwhile 条件不成立直接返回 slow 即节点1正确。如果你写的是数组缓存的解法空链表会返回 nodes[0]直接越界。这就是我为什么说数组缓存只适合作为思路补充不适合当主解——它在边界处理上不够干净。4.2 偶数长度链表的输出节点偶数长度是这道题最大的考点。我再把关键场景强调一遍。链表 1-2-3-4两个中间节点是节点2和节点3题目要节点3。快慢指针同时从 head 出发一轮后 slow 到节点2、fast 到节点3此时 fast.next 节点4 不为空继续第二轮slow 到节点3、fast 越过节点4变成 null。循环退出slow 停在节点3正确。链表 1-2-3-4-5-6期望节点4。快慢指针会执行三轮slow 依次到节点2、节点3、节点4fast 依次到节点3、节点5、null然后退出正确。如果面试官给偶数长度的用例你写之前可以先口算一遍快指针走完一轮的位置决定了 slow 的最终位置。你越能快速口算这些用例面试官对你就越放心。4.3 我每次提交前都会跑的五个用例刷这种链表题我不建议只靠LeetCode的官方用例。我会在本地或草稿纸上准备一组覆盖各类情况的测试用例每次写完代码都过一遍形成固定习惯。这一题我用的是下面这组链表内容期望输出说明nullnull防御性测试[1]节点1单节点[1,2]节点2偶数双节点取靠右[1,2,3]节点2奇数三节点[1,2,3,4]节点3偶数四节点取靠右[1,2,3,4,5,6]节点4较长偶数多走几轮验证这套用例的覆盖逻辑是空、最短奇、最短偶、普通奇、普通偶、再长一点的偶。所有边界都被扫到。如果你在面试时能说出我平时会用这几种用例自测这本身就是一个加分的信号。5. 链表中点不是终点而是兄弟题的预制件5.1 在回文链表与重排链表里它是第一步Hot 100列表里链表中点这个操作经常作为某道难题的第一步出现。最典型的是回文链表LeetCode 234和重排链表LeetCode 143。回文链表的思路是先找到中间节点然后把后半段链表反转再和前半段逐节点比较。如果中间节点找错后半段起点就错了回文判断必然出错。你想想234题前面有一大堆翻转、比较逻辑要处理结果第一步就翻车后面全完。重排链表更典型它要求把链表从 L0-Ln-L1-Ln-1-L2-Ln-2 的顺序重新排列。标准解法是三步快慢指针找中点、把链表分成两半、反转后半段、交替合并。没有链表中点这个预制件这道题你连动手的入口都找不到。所以我在刷Hot 100时会特意把876这种工具型题目打上标记每次刷到兄弟题就直接引用它作为前置知识点不用重新推导。5.2 从找中点到找倒数第K个节点和环形链表双指针的大类里找中间节点和找倒数第K个节点是同一套思想的两种体现。找倒数第K个节点时让 fast 指针先走 K 步然后 slow 和 fast 再同步前进当 fast 到达末尾时 slow 正好停在倒数第K个节点。这和找中间点的逻辑同构——都是让两个指针之间保持一个固定偏移利用终点位置反推出目标位置。区别只是偏移是 n/2 还是 K。环形链表LeetCode 141、142也是双指针的另一分支慢指针每轮走一步快指针每轮走两步如果有环两个指针最终会相遇。这和找中点的代码长得几乎一模一样只是循环条件不同——找中点以 fast 是否到达末尾为退出条件环形链表以 slow 是否追上 fast 为判定条件。我经常跟刷题的朋友说双指针在链表里就三件事找中点、找倒数第K个、判断环。你把这三种模型练成一个整体比一道一道孤立地刷效率高得多。6. 面试现场这样讲思路代码反而写得更顺6.1 写代码之前用两句话说清方案现场写代码之前我建议你先用两句话把自己的方案讲完整而不是抄起编辑器就敲。这两句话大概是这样的我会用两个指针同时从头节点出发慢指针一次走一步快指针一次走两步。快指针到达链表末尾时慢指针正好在中间。循环条件是快指针和它的下一个节点都不为空这样奇数和偶数长度的链表都能正确处理。注意这句话里包含了三个信息指针速度、返回位置、终止条件。你说完这三件事面试官就已经知道你理解了这道题的关键。后面写代码的容错率会高很多。6.2 最容易写崩的三个细节我复盘过很多次的代码提交发现这道题的翻车点高度集中在三个地方第一fast 初始化成了 head.next导致偶数链表返回靠左的中间节点。这个问题在3.3节说过你只要记住同时从 head 出发就不会踩坑。第二while 条件只写了 fast.next没有写 fast。这种情况在奇数长度链表上能跑但是一旦链表长度是偶数循环会在 fast 为 null 时尝试访问 fast.next直接抛空指针。Java和C尤其容易在这里崩。第三把 slow 和 fast 的步进顺序写反先让 fast 跳两步再让 slow 走一步。因为 fast 的移动依赖 slow 当前的位置吗不依赖。但是逻辑上先走 slow 再走 fast 更符合每回合同时移动的直觉也方便你口述每轮慢走一步快走两步。如果先 fast 后 slow口述和代码不一致面试官可能会追问反而增加出错概率。还有一种写法是 while fast.next and fast.next.next我前面提过不建议用。它虽然不会空指针但对偶数长度链表会少走一轮导致返回靠左节点。也就是说有些代码能跑但答案不对这种最危险。6.3 我的复盘习惯每刷完一道题我都会做一个三分钟复盘步骤是先凭记忆把代码重写一遍重点检查退出条件再想这道题能拆成哪些子问题能用在哪些后续题目上最后在笔记本上写一句话总结。这一题的总结我写的是876考点不在找中点在于明确偶数长度返回靠右节点所以快慢指针必须同时从 head 出发循环条件必须同时判断 fast 和 fast.next。后来刷回文链表和重排链表时我反复用这同一个原理一次都没跑偏。我也建议你试试这个习惯特别是这种代码很短但边界很多的小题——如果不复盘今天能过一周后再写很可能又在同一个地方卡住。
