LeetCode Hot100刷到第23题正好是 142. 环形链表 II。说实话这道题我最早是背答案过的——快慢指针相遇之后把慢指针放回头节点两个指针再一起走再次相遇的地方就是环入口。但背答案和真正理解之间隔着一道证明的距离。面试的时候面试官几乎必问“为什么第二次相遇就是入口”答不上来就很尴尬。这篇就把这道题从暴力解到最优解、从代码到数学证明完整捋一遍顺便把我在实际刷题中踩过的坑、以及面试追问的常见套路都整理出来。内容按难易递进如果你只是想要一个能跑的答案可以直接跳到第5章的代码如果你想彻底搞清楚背后的原理建议从头看。1. 先分清两道题判断有环和找到环入口是两回事1.1 141题和142题之间的关系LeetCode 141问的是“链表有没有环”判断题返回布尔值。LeetCode 142问的是“环的入口在哪里”返回节点。两者确实共用同一个前置动作——快慢指针相遇判断但142多出来的那一截才是真正的考点。很多人刷141的时候用的是“快慢指针能遇上就有环”这个结论代码写得很顺。到了142第一反应是那我在141的基础上快慢指针第一次相遇的地方不就是环里的节点吗把它返回不就完了这正好是这道题最大的陷阱。我第一次做142的时候就是这么想的提交之后发现答案不对当时还觉得是LeetCode判题出问题了。后来把环画出来才明白快慢指针的第一次相遇点由环长和链表头到环入口的距离共同决定它是一个“随缘”的位置跟环入口没有固定关系。你只能确定它一定在环内但不能确定它就是环的起点。1.2 第一次相遇点为什么不是入口举个例子你就明白了。链表是 1 → 2 → 3 → 4 → 5 → 6然后 6 又指向 3那么环入口是 3。让快指针每次走两步、慢指针每次走一步两者从 1 出发。模拟一下慢指针走到 2 时快指针到 3慢指针到 3 时快指针到 5慢指针到 4 时快指针到 3慢指针到 5 时快指针到 5。第一次相遇点落在 5可入口明明是 3。看到了吧用“第一次相遇点直接当入口”是错的。那为什么另一套做法——把一个指针放回头节点再一起走第二次相遇就一定是入口这背后是Floyd判圈算法的数学性质需要用等式推一遍才能真正放心用。这道题LeetCode的进阶要求是 O(1) 空间也就是说哈希表能过但不是出题人想要的答案。要拿到面试加分快慢指针加数学证明这条路线才是完整答案。2. 哈希表解法最直观的基线方案以及它的空间代价2.1 哈希表思路与代码环入口有一个等价定义链表里第一个被访问两次的节点。因为链表是单向的一旦进入环就会在环内无限绕圈。从 head 开始遍历第一个出现“已经见过”的节点必然是环的入口而不可能是环里的其他位置。想清楚这点哈希表解法就是几分钟的事。import java.util.HashSet; import java.util.Set; public class Solution { public ListNode detectCycle(ListNode head) { SetListNode seen new HashSet(); while (head ! null) { if (seen.contains(head)) { return head; } seen.add(head); head head.next; } return null; } }时间 O(n)空间 O(n)。这个方案最大的优势是直观、正确性一眼能看懂适合作为写最优解之前的热身。你甚至可以把它当作验证工具拿随机用例跑一遍哈希表解法再用快慢指针解法跑一遍两边结果一致能帮你确认自己的最优解实现没写歪。2.2 空间代价与“打标记”方案的取舍面试时如果你先给出哈希表面试官大概率会追问一句能不能把空间降到 O(1)“能Floyd 快慢指针。”回答到这里这道题的深度才算开始体现。还有一类解法要特别提醒有人会在遍历过程中修改节点的 val比如标记成某个特殊值第二次遇到这个特殊值就认为是入口。这样做在本地测试能过但它破坏输入数据工程上是大忌。链表作为入参调用方可能还在别处持有引用你改完以后人家再用就出事。真要讨论这种方案一定要主动说“会修改原数据所以不推荐”反而能给面试官留下边界意识强的印象。对这道题而言哈希表和打标记都是“能解但不优”的方案。LeetCode 的进阶要求明确写了空间 O(1)所以快慢指针才是这道题的主菜。3. 快慢指针的相遇逻辑为什么快指针走两步快慢指针一定会碰上3.1 Floyd判圈算法的两个阶段Floyd 判圈算法分两段。第一阶段快指针每次走两步慢指针每次走一步如果链表有环两者必然相遇第二阶段把一个指针放回 head另一个留在第一次相遇点然后两个指针都变成每次走一步再次相遇的位置就是环入口。第一阶段还比较好理解快指针先进环慢指针后进环之后快指针相对慢指针每轮逼近一步距离只会越来越近不会出现“永远差一步”的情况。第二阶段是所有人懵掉的地方——为什么都变成一步之后一定会在入口碰头要回答清楚必须上数学。这一章先解决“为什么第一阶段快慢指针一定相遇”下一章再算“为什么第二阶段相遇点就是入口”。3.2 为什么快指针固定走两步而不是三步先讨论一个常见疑问快指针能不能一次走三步或四步从“能不能找到环”的角度快指针走三步也大概率能碰上慢指针但有两个问题第一速度差变为 2快指针可能直接跨过慢指针所在的节点导致“明明应该碰上却错过了”。虽然绕几圈之后最终还是可能追上但这个追赶过程变得复杂很难用简单的距离缩短来解释。走两步时速度差为 1每一轮两者的相对距离严格减 1绝对不会跳过。第二LeetCode 和面试里讨论的 Floyd 算法标准速度比就是 2:1。你非要走三步虽然能跑通部分测试用例但被追问“如何证明一定能相遇”时会非常被动。考场上最怕的不是不会做而是做出来了却解释不清原理。所以结论很简单快指针一次走两步速度差为 1追及过程最干净数学证明也最完整。别贪那一步没必要。还有一个实现细节快慢指针都从 head 出发比“快指针从 head.next 出发”要少一个空指针分支第二阶段也不需要额外处理“入口就是 head”的情况。从同一个起点出发是代码最简单、思维负担最小的写法。4. 环入口的数学推导用一条具体链表把每一步算给你看4.1 三个符号搞定整个推导设链表从 head 到环入口的距离为 a。设环入口沿前进方向到第一次相遇点的距离为 b。设第一次相遇点继续沿前进方向回到环入口的距离为 c。那么环长 L b c。第一次相遇时慢指针一共走了 a b 步。快指针是慢指针速度的两倍所以快指针走了 2(a b) 步。但快指针还可能在环里绕了 n 圈n ≥ 1所以快指针的路程也可以写成 a b nL。于是有2(a b) a b nL化简得到 a b nL再变形a nL - b n(b c) - b (n - 1)L c这个式子是全题的灵魂。它的意思是从 head 走到环入口距离 a正好等价于从第一次相遇点出发、绕 n - 1 圈之后再走 c。也就是说如果你让一个指针放在 head一个指针放在第一次相遇点两个指针同时以一步的速度往前走走完 a 步之后它们都会停在环入口。4.2 代入一条具体链表把推导跑一遍继续用之前的例子1 → 2 → 3 → 4 → 5 → 6然后 6 指向 3。入口是 3。这里 a 2从 1 到 3 需要走两步不算入口节点本身环长 L 43 → 4 → 5 → 6 → 3。慢指针第一次与快指针相遇在 5。从 3 到 5经过 3 → 4 → 5所以 b 2。从 5 回到 3经过 5 → 6 → 3所以 c 2。代入公式a (n - 1)L c也就是 2 (n - 1) × 4 2得到 n 1说明快指针在第一次相遇前只在环里绕了完整的一圈符合我们刚才的模拟。第二阶段慢指针回到 head即节点 1。快指针留在 5。两个指针都一次走一步慢指针走两步到 3快指针从 5 出发走两步经过 6 到 3。两者在 3 相遇而 3 正是环入口。把 n 2 的情况也代一下如果快指针绕了两圈才碰到慢指针公式会推出 a L c。含义是从 head 走到入口的距离等于从相遇点绕一整圈再多走 c 到入口。无论 n 是几结果都不变——一个从头走、一个从相遇点走同速前进一定在入口汇合。4.3 入口就是头节点的特殊情况还有一种情况偶尔会见到head 本身就在环入口比如 1 → 2 → 3然后 3 指回 1。这时 a 0。按公式走第一次相遇后把 slow 放回 headfast 留在相遇点。由于 a 0slow 走 0 步就到入口fast 从相遇点走 0 步也就是在入口。因为相遇点恰好就是入口本身。此时循环条件如果写成 “while (ptr ! slow)” 会直接判断失败然后返回 head逻辑上刚好成立。但如果你把循环条件误写成 “while (ptr.next ! slow.next)”入口是 head 的情况下可能直接跳过判断返回错误结果。这种边界细节正是后面要展开说的。5. 代码实现细节与三种边界情况空链表、单节点、全环5.1 可运行的完整实现Java Python数学推导到位之后代码只是翻译。先看 Java 版本public class Solution { public ListNode detectCycle(ListNode head) { if (head null || head.next null) { return null; } ListNode slow head; ListNode fast head; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { // 第一阶段相遇说明有环 ListNode ptr head; while (ptr ! slow) { ptr ptr.next; slow slow.next; } return ptr; // 第二次相遇点就是环入口 } } return null; // 快指针走到 null说明无环 } }再看 Python 版本逻辑完全一致class Solution: def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]: if head is None or head.next is None: return None slow head fast head while fast is not None and fast.next is not None: slow slow.next fast fast.next.next if slow is fast: ptr head while ptr is not slow: ptr ptr.next slow slow.next return ptr return None这段代码有几个地方是刻意设计的。比如第一行就处理了空链表和单节点无环的情况省掉后面 while 循环里额外的判空分支。再比如第二阶段用的是 “while (ptr ! slow)” 而不是 “while (ptr.next ! slow.next)”原因前面提过前者天然覆盖“入口就是 head”的全环场景后者在特殊用例下会翻车。5.2 三种边界情况逐一验证写这题最容易出事的场景我用一张表总结一下用例结构预期输出代码行为空链表nullnull第一行直接返回 null单节点无环1 → nullnull第一行直接返回 null双节点无环1 → 2 → nullnullwhile 里 fast 先到 null返回 null普通带环链表1 → 2 → 3 → 4 → 5 → 6 → 3节点 3第一阶段相遇在 5第二阶段在 3 汇合头节点就是入口1 → 2 → 3 → 1节点 1第一阶段相遇后ptr 和 slow 已经相等直接返回 head单节点自环1 → 1节点 1slow 和 fast 第一步就相遇第二阶段直接返回 head最后一行单节点自环的用例我用 LeetCode 的判题系统实测过。链表节点是 1next 指向自己快慢指针都从 head 出发第一次循环 slow 走到 1、fast 走到 1立即相遇。然后 ptr head 1slow 也是 1循环条件 ptr ! slow 为 false直接返回 head。整个逻辑完全闭环。5.3 常见翻车点清单围绕这段代码我整理几个刷题时最容易踩的坑第一while 的判断条件 “fast ! null fast.next ! null” 两个条件不能换顺序也不能漏第二个。fast.next 为 null 时访问 fast.next.next 会直接空指针异常。有些题解为了省事写 “while (fast ! null)”在无环链表的倒数第二个节点上就会崩。第二第二阶段别把 fast 也重置回 head。有网友分享过一种写法第一阶段相遇后让 fast head然后 fast 和 slow 一起走。这个思路本身对但如果你把 slow 也一起重置那就完全错了。正确做法是二选一要么 slow 回 head、fast 留在相遇点要么 fast 回 head、slow 留在相遇点。只要有一个指针从 head 重新出发另一个从相遇点出发就行。第三返回 null 的位置不能乱放。很多人在循环结束后直接返回 null这是对的但要注意第一阶段里如果走了 “if (slow fast)” 并做了 return循环外的 null 只能由无环情况走到。两个 return 路径不要混淆。第四别把 141 的代码直接改个返回值就当 142 交上去。141 相遇后直接 return true142 需要在相遇之后再做第二阶段。漏掉第二阶段返回的就是第一次相遇点这道题的判题器会告诉你答案错了。6. 面试追问与刷题延伸从这道题能带到哪些常见考点6.1 面试官最常追问的三个问题这道题在面试里的讨论深度通常不止“写出来”这么简单。我总结三个高频追问可以提前准备追问一“为什么第二次相遇就是环入口”这是必问题。把第 4 章的公式推导用两分钟讲清楚比报答案高级得多。核心就是那个等式a (n - 1)L c。能写出这个式子面试官基本就会点头放过你。追问二“如果链表很长、环很小两种解法的时间复杂度有什么区别”哈希表是 O(n) 时间、O(n) 空间快慢指针是 O(n) 时间、O(1) 空间。需要额外注意快慢指针在无环情况下的时间复杂度上限是遍历整个链表有环情况下是慢指针在环内走不到一圈就会被追上整体仍然是 O(n)。这点可以主动补充显得你考虑过复杂度细节。追问三“为什么不用修改节点值的方式找入口”回答要点是修改输入数据是不安全的链表可能被其他代码共享引用而且 LeetCode 142 也没有允许修改节点。你要表达的是“我考虑过这个方案但它破坏数据所以不是好方案”而不是“我没想过”。6.2 同构题287. 寻找重复数的快慢指针解法如果你把 142 吃透了有一道题可以直接复用这套思路LeetCode 287. 寻找重复数。题目给一个长度为 n 1 的数组里面数字都在 1 到 n 之间只有一个数字重复要求不修改数组、只用 O(1) 空间找出来。它的经典解法就是把数组抽象成一条隐式链表把下标 i 当作节点把 nums[i] 当作 next 指针。因为 nums[i] 的取值范围是 1 到 n刚好可以指向另一个下标这样就构造出一条“数组链表”。重复数字在数组里出现两次等价于有两个下标指向同一个节点也就是环的入口。于是 287 的核心就变成了“找隐式链表的环入口”和 142 的解法完全同构。我个人很推荐刷完 142 之后立刻去做 287你会发现原来快慢指针不仅适用于链表也适用于一切能抽象成“节点 next 指针”的结构。这种迁移能力才是刷题真正的收获。6.3 刷题建议Hot100 的题单里141 和 142 基本是捆绑出现的。我建议把两道题放在同一天刷先 141 再 142。141 让你掌握快慢指针的相遇判断142 再进一步要求你推导入口位置难度递进很自然。如果你时间充足还可以顺手看一眼 876. 链表的中间结点它用的是同一套快慢指针找位置的思路快指针走两步、慢指针走一步快指针到底时慢指针正好在中间。你会发现所谓“快慢指针”本质上就是用两个不同的速度制造一个可预测的相对位移从而定位链表里的特殊位置。把这个抽象想透了这一类题的底层逻辑你就全掌握了。最后说点我自己刷这道题的感受吧。第一次背答案过掉之后我其实一直觉得这题“会了但不是真的会了”直到某天自己手动在纸上画了一条带环的链表把 a、b、c 一个个标出来才算彻底踏实。现在我做 141 和 142只要一分钟就能写完但每次还是会提醒自己对环入口的数学理解比代码本身重要得多。建议你也别急着背模板拿笔把第 4 章的推导走一遍再回来写代码肯定会有不一样的感觉。