刷LeetCode Hot 100刷到第23题的时候我终于碰到了环形链表 II。这题在面试里的出现频率非常高不管是校招还是社招只要考链表面试官很容易往上加这一问——先让你判断有没有环紧接着追问“那环的入口在哪”。Hot 100把这个题标为中等难度但很多人在第一阶段的“快慢指针相遇”还能跟上一到第二阶段为什么要重新从头走一遍就懵了。这篇我把整个题的推导、代码、边界条件、面试扩展全部拆开讲清楚适合正在按 Hot 100 刷题、准备面试的朋友直接参考。1. 题目是什么Hot 100 第 23 题到底在问什么1.1 从题目描述看起不是判断有环而是找到环的入口题目本身很短给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。注意这个表述和 141 环形链表 I 的区别。141 只问你“有没有环”返回布尔值142 直接要求把环的入口节点拿出来。不要小看这一字之差它意味着你不仅要在链表里确认存在环还要精确定位环是从哪个节点开始的。举一个具体场景链表3 - 2 - 0 - -4并且-4的 next 指向2那么环的入口就是节点2。很多人第一次看到这个例子会觉得挺直观但真到了代码层面就发现单纯判断有环的方法没法告诉你入口在哪。这也是这道题作为“中等题”而不是“简单题”的原因它需要一点数学推导能力。1.2 为什么这题值得单独写一篇在 LeetCode Hot 100 里链表类题目有十来道142 是比较典型的一道“看着简单、做起来发懵”的题。第一它考察的不只是指针操作还有对循环不变量的理解。第二它的两个经典解法——哈希集合法和快慢指针法——分别代表了“空间换时间”和“数学推导优化空间”两种思路正好是面试里喜欢对比的两种方案。第三它的变体特别多比如求环的长度、判断两条链表是否相交、寻找重复数都能用同样的思想解决。我自己的经验是如果能把 142 的推导过程从头到尾讲清楚面试官对你这部分的评价一般不会低。因为大多数人只会写代码能讲明白“为什么相遇后再走一定能找到入口”的人确实不多。2. 解题思路拆解为什么哈希简单快慢指针高级2.1 哈希集合解法用空间换清晰第一种解法最容易想到遍历链表把每个节点存进哈希集合如果某个节点已经存在说明这就是环的入口。这个思路本质上利用了“链表的节点引用唯一”这个特性。class Solution: def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]: seen set() cur head while cur: if cur in seen: return cur seen.add(cur) cur cur.next return None复杂度方面时间 O(n)空间 O(n)。这里的 n 是链表节点总数。很多人觉得这个解法“太简单了”但我不建议在面试中一上来就否定它。如果面试官没有额外要求哈希集合法是正确且稳妥的。它最大的价值是思路清晰不容易出 bug特别适合快速搞定问题再优化。但哈希法也有一个明显的短板空间复杂度 O(n)。面试官大概率会追问一句“能不能做到 O(1) 空间”这就轮到快慢指针出场了。2.2 快慢指针O(1) 空间背后的关键思路快慢指针也叫 Floyd 判圈算法核心是让慢指针slow每次走一步快指针fast每次走两步。如果链表有环两个指针最终会在环内相遇如果没有环快指针会先到达链表末尾。这里有一个常常被忽略的点为什么有环时两个指针一定会相遇因为快指针每次比慢指针多走一步相当于在环里每次靠近慢指针一步。只要环存在快指针迟早会和慢指针重合。但题目要的是入口节点不是相遇点。所以快慢指针要分成两个阶段第一阶段slow每次走一步fast每次走两步找到相遇点。第二阶段让一个指针从head重新出发另一个从相遇点出发都是一次走一步。它们再次相遇的位置就是环的入口。第二阶段这句话看起来像魔法其实背后有严格的数学推导。下一节我会把整个推导过程完整展开包括第一阶段为什么慢指针不会在环里绕圈、快指针为什么会多跑几圈。3. 数学推导为什么慢指针再走 L 步就能找到入口3.1 先把变量定义清楚设链表头节点到环入口的距离为a环入口到两个指针第一次相遇点的距离为b相遇点继续走到环入口的距离为c。那么环的长度L b c。需要注意的是a有可能为 0也就是头节点本身就是环的入口这个边界后面会专门讲。b和c都是非负整数并且当环只有一个节点时b 0。3.2 关键等式推导相遇点就是入口的入口第一阶段slow进入环后两个指针都在环内运动。假设它们第一次相遇时slow走了s步fast走了2s步。slow的路径是a b所以s a bfast的路径是a b再加上若干圈完整的环。假设fast比slow多走了n圈那么2s a b n * L把s a b代入第二个等式2(a b) a b n * L a b n * L重点来了把等式变形a n * L - b再把L b c代进去a n * (b c) - b a (n - 1) * (b c) c这个式子说明什么从链表头走到环入口需要走a步从相遇点继续走走(n-1)圈再加上c步也会到达环入口。所以只要你让一个指针从head出发另一个指针从相遇点出发两者都以每次一步的速度前进它们必然会在环入口相遇。这里注意一点第二阶段两个指针走的步数不同。从head出发的指针要走a步从相遇点出发的指针要走(n-1)*L c步。但因为等式成立它们在环入口相遇的时间点是相同的。这就是“为什么走到入口处会碰头”的完整原因。3.3 快指针多走的圈数和慢指针为什么不会在环里绕圈很多人会追问一个细节n到底等于多少实际上n是大于等于 1 的整数具体值取决于链表结构但不影响最终结论。另一个常见的疑问是慢指针进入环后会不会在相遇之前就绕着环走了很多圈答案是不会。这里有一个容易忽略的证明。当slow刚进入环的入口时fast已经在环内某处了。因为fast的速度是slow的两倍相当于每一个单位时间fast相对slow靠近一步。环的长度是L在slow进环的那一刻fast离slow最远也就是L - 1步所以最多再走L - 1步fast就能追上slow。也就是说从slow进环到两者相遇slow在环内走的路程一定小于一圈。这也解释了为什么第一阶段结束后slow和fast的相遇点是唯一的。理解了这部分推导面试时就算面试官临场换个问法比如“如果快指针每次走三步这个结论还成立吗”你也知道问题出在哪快慢指针的步长差不再是 1推导中的相对速度会变结论就可能失效。4. 代码实现与边界条件实际调试里踩过的坑4.1 快慢指针的标准实现直接贴可以跑的 Python 代码注释写清楚每一段的意图class Solution: def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]: slow head fast head # 第一阶段找到第一次相遇点 while fast and fast.next: slow slow.next fast fast.next.next if slow fast: # 第二阶段从头节点和相遇点同时出发 ptr head while ptr ! slow: ptr ptr.next slow slow.next return ptr # 无环 return None为什么第一个while的条件是fast and fast.next因为fast每次走两步如果fast本身是空或者fast.next是空说明链表已经走到末尾必然无环。如果不加fast.next的判断代码在访问fast.next.next时会报空指针异常。第二阶段为什么不会死循环根据前面的推导从头节点出发的指针走a步从相遇点出发的指针走(n-1)L c步两者必然在入口相遇。也就是说这个while循环的终止条件是确定的不会出现两个指针永远不相遇的情况。4.2 哈希集合实现简单但够用class Solution: def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]: seen set() cur head while cur: if cur in seen: return cur seen.add(cur) cur cur.next return None两种算法的时间复杂度都是 O(n)区别只在空间复杂度。面试时可以先把哈希版写出来然后主动说“如果要求 O(1) 空间我还可以用快慢指针优化”这样反而显得你对复杂度有意识。4.3 边界条件与复杂度分析我整理了几个实际刷题和面试中容易出问题的地方按重要性排个序场景现象处理方式空链表head为 None循环进不去直接返回 None单节点无环fast.next为 None循环条件不成立返回 None单节点有环节点 next 指向自己在slow fast处返回该节点头节点就是入口a 0第二阶段 ptr 从 head 出发马上与 slow 相遇返回 head环特别长快指针可能绕好几圈数学推导中n 1不影响代码逻辑环特别短慢指针进环后马上相遇第二阶段步数少代码仍然正确空间复杂度哈希集合法 O(n)快慢指针法 O(1)。时间复杂度上第一阶段最坏情况下慢指针走a L步以内就会相遇第二阶段最多再走a步总步数仍然控制在 O(n)。这里给一个建议刷题时不要只满足于把所有测试用例跑通可以自己构造几个特殊用例跑一遍。比如一个两节点且第二个节点指向第一个节点的环很多人第一次写快慢指针就在这里栽过原因是不理解fast.next的判断顺序。5. 刷 LeetCode 的实战心得Hot 100 节奏与题目迁移5.1 环形链表 II 的变体与迁移做完 142 之后有几道题你会觉得特别眼熟因为它们本质上都在用同一套思想。第一求环的长度。这个最简单找到相遇点后让一个指针停住另一个指针每次走一步再次相遇时走过的步数就是环长。第二判断两条链表是否相交。经典做法是把其中一条链表的尾节点接到头节点构造出一个环然后问题就变成了“找环的入口”入口就是两条链表的交点。第三LeetCode 287 寻找重复数看着是数组题但利用“索引当成指针”的思路它就是一个隐藏的链表找环问题。第四快乐数的判断逻辑同样可以用快慢指针检测循环。这些题目之间的关联其实是刷 Hot 100 最值得花时间的地方。你每做完一道题去翻一翻同类型的题会发现自己的方法论越来越成体系。5.2 快慢指针思想在更多场景中的应用快慢指针不只适用于链表环检测。数组里的循环检测、字符串里的重复模式判断、以及一些需要“检测是否陷入循环”的逻辑都可以迁移这个思想。比如检测一个函数是否会陷入死循环时如果无法预知迭代次数就可以用快慢指针的方式探测状态是否会重复。这听起来抽象但实际在处理一些自定义迭代器、状态机的时候这招特别有用。我甚至见过有人拿这个思路去分析程序里某个状态是否会无限循环虽然生产环境里不会有人真这么写但至少说明这个思想的通用性。再补充一个面试中常被追问的点为什么快指针一定要走两步不能走三步核心在于“相对速度”。走两步时快指针相对慢指针每次靠近一步走三步时则是靠近两步。从数学上看走三步依然能相遇但推导式中要处理“跳过头”的情况两个指针可能在环内错过数次分析起来会更复杂。面试中如果主动提到这一点能展示你对算法细节的理解深度。5.3 按 Hot 100 刷题的个人节奏建议Hot 100 总共 100 题我自己的感受是按专题刷比按题号顺序刷效率高。链表类题目集中做一遍树类题目集中做一遍动态规划再集中做一遍这样你会在短时间内反复用到同一套思路记忆更牢。142 处在 Hot 100 的第 23 位左右正好是很多人口中的“前 25 题劝退区”。说实话前二十五题里混着不少看起来简单、实际很深的题环形链表 II 就是其中之一。如果刷到这里卡住了不要太纠结可以先看题解把推导写在草稿纸上过两天再独立写一遍。我做这道题时也是第二遍才完全理清数学推导的每一步第三遍才做到不看任何参考直接写出无误代码。刷题本来就是循环过程没必要给自己太大压力。6. 最后分享一点面试用法与复盘技巧如果你是在准备面试建议把这道题准备成“可以手写推导的题目”。面试官如果让你做环形链表 II通常期待你能边说边写讲清楚为什么第一阶段找到相遇点之后第二阶段还要从头再走一遍。如果你能顺手把a (n-1)L c这个等式写在纸上再对照代码解释每一步面试效果会非常稳。还有一个我自己常犯的错误在这里提醒一下第一阶段用while循环找相遇点的时候如果不小心把slow slow.next写成slow fast.next或者把fast fast.next.next写成fast fast.next很容易出现逻辑正确但死循环的情况。刷题时多用几个用例验证面试时先写框架再填细节能少踩很多坑。另外如果你做的是 JavaScript 版本特别注意ListNode虚拟机环境里可能没有定义但 LeetCode 会帮你处理好。本地调试时可以用{ val, next }字面量自己构造链表方便测试。不管用什么语言核心逻辑都一样做题时把语言特性搞明白面试时才不会因为语法问题卡壳。