要搞懂这道“环形链表Ⅱ”光会判断有没有环远远不够。很多人在 LeetCode-141 里用快慢指针跑得飞起一遇到 142 要找入环点就直接懵住。LeetCode-142 真正考的不是“会不会用双指针”而是“能不能讲清楚快指针和慢指针相遇之后下一步为什么能精确找到环的入口”。这个细节就是拉开差距的地方。我自己的体会是这道题适合放在链表刷题的中段来做。前面已经熟悉了链表遍历、节点操作、边界判断再做 142 就顺理成章。这次我写这篇记录完整拆一遍从题目理解、数学推导到代码落地的全过程把那些“代码一写就过、但面试一追问就卡壳”的点全部摊开讲明白。1. 题目定位与整体思路拆解1.1 这题到底在问什么LeetCode-142 的全称是“环形链表 IILinked List Cycle II”。题目给一个链表的头节点要求判断链表是否有环如果有环返回环的入口节点如果没有环返回null。注意这里和 141 最大的区别141 只问“有没有环”返回布尔值142 问“环在哪”返回具体节点。输入示例是head [3,2,0,-4]pos 1表示尾节点指向下标为 1 的节点。这里的pos是题目用来描述环的位置的实际做题时我们拿不到这个值只能靠链表结构本身来判断。这道题在 LeetCode 上被标记为“中等”但它在面试里出现的频率非常高。原因很简单141 的解法直接套到这里只能算完成了一半后半程找入环点需要额外的推理。很多候选人能写出快慢指针相遇却解释不了“为什么相遇后从头再走一步两个指针就能在入口点碰上”这恰恰是面试官最想听的部分。1.2 为什么哈希表法不是最优解第一次接触这题时大多数人第一反应是哈希表。思路很直接遍历链表每到一个节点就存进哈希集合如果发现某个节点已经存在那么这个节点就是环的入口。这个方案写起来很简单public ListNode detectCycle(ListNode head) { SetListNode seen new HashSet(); ListNode cur head; while (cur ! null) { if (seen.contains(cur)) { return cur; } seen.add(cur); cur cur.next; } return null; }时间复杂度 O(n)空间复杂度 O(n)。功能上完全正确但有两个问题一是面试官大概率会追问“能不能不用额外空间”二是哈希表方案虽然直观但没有触及环形链表结构的本质。而快慢指针Floyd 判圈算法能做到时间 O(n)、空间 O(1)这也是它成为标准答案的原因。不过我得说句公道话哈希表法不是一无是处。笔试时如果为了赶时间哈希表是快速拿分的稳妥方案但在面试场景里最好主动给出快慢指针版本并且能顺手解释清楚推导过程。这也是我在刷题记录里一直强调的——“能跑通”只是及格线“能讲明白”才是加分项。1.3 快慢指针解决这题的三步走快慢指针的核心思想是一个生活常识的抽象化两个人在环形跑道上跑步速度快的人最终一定会追上速度慢的人。放到链表里快指针每次走两步慢指针每次走一步如果链表有环两者必然在某个节点相遇。但 142 比 141 多了一步。完整流程拆出来是三段快慢指针同时从 head 出发判断链表是否有环如果无环直接返回 null。如果相遇说明有环。此时把慢指针重新拉回到 head 位置快指针保持在相遇点不动。然后两个指针都改为每次走一步继续前进。它们再次相遇时所在的节点就是环的入口。第三步是整道题的精髓。很多代码模板直接把这个过程写出来但没有人告诉你为什么这一步能成立。如果只是背代码换个场景很容易露馅。所以接下来的数学推导是这篇文章最值得看的部分。2. 数学原理拆解为什么重新出发就能找到入环点2.1 用变量把环的结构描述清楚要推导相遇点与入环点的关系先得定义几个距离。假设从链表头节点到环入口节点的距离为a从环入口节点到快慢指针第一次相遇节点的距离为b从第一次相遇节点继续向前走回到环入口节点的距离为c。由此可知环的周长L b c。画个示意图的话就是链表头出发一段直线走到入口进入环之后先走b到达相遇点再走c回到入口完成一整圈。这里我用“距离”指的是经过的节点个数。比如a 0的情况就是链表头就在环入口上这种情况在实际代码里也经常出现比如一个自环的节点。2.2 从速度关系推导关键等式快指针速度是慢指针的两倍意味着在相同时间内快指针走过的路程是慢指针的两倍。假设慢指针从 head 出发到第一次相遇一共走了a b这么长的距离。快指针呢它走了a b之后还会在环里继续绕圈。由于它在追上慢指针之前可能已经在环里绕了好几圈所以快指针总共走的路程是a b kL其中k是快指针在环内完整绕过的圈数k 1。速度两倍关系可以写成等式2 * (a b) a b kL两边同时减去a b得到a b kL这个式子非常关键。它表达了链表头到相遇点的距离a b正好等于环周长的整数倍。继续变形。把L b c代入a b kLa b k(b c) a k(b c) - b a (k - 1)(b c) c最后得到a (k - 1)L c这个式子的含义是从链表头到环入口的距离a等于从相遇点出发先走c到达环入口然后再绕k - 1圈的路程。2.3 式子的直觉理解与指针行为对应直觉上a (k - 1)L c说明了一件很有意思的事情如果让一个指针从链表头出发另一个指针从相遇点出发两者都保持每次走一步那么当第一个指针走过a到达环入口时第二个指针走过的路程是(k - 1)L c。因为第二个指针本来就在相遇点而相遇点到环入口的距离恰好是c所以第二个指针在走了c之后到达环入口剩下的(k - 1)L就是完整绕圈最终也会停在环入口。两个指针在环入口碰上了。这就是代码里“慢指针回到 head然后两个指针同步走相遇点即入口”的数学依据。我最初做这道题的时候卡在a (k - 1)L c这个式子上很久。后来用一个具体例子验证假设环特别大k 1那么a c。意思是链表头到入口的距离恰好等于相遇点绕回入口的距离。代码跑起来的结果和推导完全一致。后面做多了这类题我发现这种“先数学推导再拿具体数值验证”的方法对理解算法题特别管用。3. 代码落地与边界条件处理3.1 一套标准 Java 实现完整的 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) { break; } } // 如果快指针走到了链表末尾说明无环 if (fast null || fast.next null) { return null; } // 第二阶段slow 回到头节点fast 留在相遇点 slow head; while (slow ! fast) { slow slow.next; fast fast.next; } return slow; } }代码很精炼核心就两个循环。但精炼的代码背后容易藏三个容易踩的坑我在 3.2 里详细说。3.2 第一次循环的退出条件怎么判断while (fast ! null fast.next ! null)这个条件很多人第一次写会漏掉fast.next ! null。如果链表没有环快指针每次走两步它可能会直接跨过链表的最后一个节点fast.next会触发空指针异常。这个条件其实是在为“无环”情况兜底同时它也承担了“有环则永远不触发”的角色只要有环快指针和慢指针永远在环里绕fast永远不会变成 null。有环时什么时候退出代码里用的是if (slow fast) break;。这个判断放在每次移动慢指针和快指针之后。遇到自环一个节点指向自己时慢指针走一步到自身快指针走两步也还是自身第一次移动后就能检测到相遇。我在刷题时还试过另一种写法把slow fast直接放到while条件里但这会引入新的问题——初始状态下 slow 和 fast 都指向 head条件必然满足循环直接退出逻辑就全乱了。所以必须用“先移动后判断”的模式。3.3 第二阶段循环的退出保障第一阶段结束后有两种可能要么 fast 走到了链表尾部无环要么 slow 和 fast 相遇了有环。第二阶段的关键是“慢指针回到 head快指针留在相遇点”。很多人在这一步想不通为什么不把快指针也重新拉回 head如果两个指针都从 head 出发再走一次那它们永远不可能在入环点相遇因为它们的步长相同会一直保持同步走到哪里都是肩并肩。第二阶段循环的条件是while (slow ! fast)每次两个指针都走一步。根据前面数学推导的结论它们必然会在环入口相遇。这个循环不需要额外的退出条件因为数学上保证了循环一定会在某个点结束。如果代码跑成了死循环大概率是第一阶段结束时对“是否有环”的判断出了差错比如漏了fast.next null的判断。4. 复杂度分析与常见误区排查4.1 时间复杂度的精确计算先给结论时间复杂度 O(n)空间复杂度 O(1)。但这里的 O(n) 值得展开说说。第一阶段慢指针走过的距离是a b其中a是链表头到入口的距离b是入口到相遇点的距离。a b 一定小于等于链表节点总数所以第一阶段的时间复杂度是 O(n)。第二阶段慢指针从 head 走到入环点走过的距离是a同样不超过 n。两个阶段加在一起总运行步数仍然与节点数量成线性关系。空间上全程只用了两个指针变量没有使用哈希表或其他线性存储结构所以空间复杂度是 O(1)。这也是快慢指针相对哈希表法最核心的优势。需要特别说明的一个点是虽然快指针在环内绕了很多圈k 圈但k的上界是有限的。快指针在追上慢指针前最多绕不超过 n 圈所以总复杂度不会因为 k 的存在变成 O(nk)。这也是为什么这个算法的常数系数虽然比哈希表法略大但渐进复杂度仍然维持在 O(n)。4.2 代码里常见的四种错误我见过不少人在讨论区贴出“差一步就过”的代码问题基本都集中在这四个地方。第一个坑漏掉空链表判断。head null时直接走fast.next必然崩溃。正确的做法是在函数开头就把head null || head.next null这种情况拦下来直接返回 null。第二个坑第一阶段快指针条件写错。写成while (fast ! null slow.next ! null)或者漏掉fast.next ! null都会在某些边界情况下抛异常。每次 fast 移动两步只要 fast 不是 nullfast.next 有可能是 null所以两个条件缺一不可。第三个坑第一阶段退出后没有判断是否有环。如果第一阶段是因为 fast 走到了末尾而退出此时把 slow 重置到 head再进入第二阶段的循环会导致死循环。因为 fast 已经是 null第二次循环里访问fast.next直接炸。所以必须先判断fast null || fast.next null然后返回 null。第四个坑把第二阶段的 fast 也重置到 head。这个错误逻辑上非常隐蔽。两个指针从同一起点同步移动永远不可能在入环点相遇除非链表只有一个节点且自环。所以第二阶段只能重置 slow不能动 fast。这四个坑我在刷题记录里都标注过每次复习都会再扫一遍。算法题很多时候不是思路想不到而是边界条件没绷住。4.3 快慢指针相遇次数带来的疑问还有一个面试官高频追问快指针和慢指针一定会相遇吗会不会出现快指针每次都“跳过”慢指针的情况这个问题的关键在于“快指针每次走两步慢指针每次走一步”两者的相对速度是一步。我们把环打开来看快指针相对于慢指针每次迭代都会逼近一个节点。想象慢指针静止不动快指针以每次一步的相对速度追赶它最终一定会碰上。那“跨过去”的场景存在吗比如慢指针在节点 A快指针在节点 A 的前一个节点快指针走两步直接跳过慢指针不会。因为快指针走两步的路径分解是先到慢指针的位置再到下一个位置。第一步就会踩到慢指针所在的节点。相对速度为 1 的追赶不存在跳过的可能。这也是为什么快指针步长必须是 2 而不是 3 的原因——步长为 3 的时候相对速度为 2就可能出现跨过一个节点却追不上的情况。我在初期试过把步长改成 3结果部分测试用例直接超时这就是数学上没想清楚导致的。5. 同类题型扩展与实战建议5.1 这题在整个链表算法体系中的位置LeetCode-142 做完之后可以顺势把下面几道题串成一组练习它们都用到了快慢指针的思想。LeetCode-141环形链表是最基础的版本只需要判断是否有环。134 题里 if 判断返回 true 或 false代码结构是 142 的子集。LeetCode-876链表的中间节点用快慢指针找中间节点快指针到终点时慢指针正好在中点。LeetCode-19删除链表的倒数第 N 个节点用快指针先走 N 步再快慢同步走快指针到末尾时慢指针停在目标节点前。LeetCode-202快乐数判断一个数是否会在变换中进入循环本质上就是把数值变化过程抽象成链表用快慢指针检测循环。这组题目刷完快慢指针的基本功就扎实了。它们的共同点都是“快慢相对速度制造差值”用差值来定位特殊位置。5.2 面试中如何把这道题讲得加分面试官让做这道题时不要上来就写代码。先口述思路把“为什么第二阶段能找到入口”讲清楚。我建议用三步走的话术先说第一阶段判断有无环“我用两个指针一个一次走一步一个一次走两步如果链表有环它们一定会在环内相遇。”再解释数学关系“遇到环后设头节点到入口的距离是 a入口到相遇点的距离是 b环周长为 L。由于快指针速度是慢指针的两倍2 * (a b) a b kL得到 a b kL进一步推出 a kL - b。”最后说明第二阶段“从相遇点继续走到入口的距离是 L - b从头节点走到入口的距离是 a而 a (k - 1)L (L - b)两者在入口处汇合。所以让一个指针从头出发一个指针从相遇点出发同步前进相遇的位置就是入口。”这样讲下来面试官能确认你不仅会写代码还真正理解了原理。我在模拟面试中试过这个讲解方式比直接甩代码的效果好很多。5.3 日常刷题记录的几个技巧这篇记录写到现在顺便分享几个我刷题过程中沉淀下来的习惯。一道题写完后我会在代码注释里补上“为什么这样写”的关键推导而不是只写“循环遍历”。比如 142 的代码注释里我会保留a kL - b这行推导方便两周后回头复习时快速唤醒记忆。每次做错题时我会记录错误类型。比如漏判边界、条件写反、数据类型不匹配每一个错误都对应一类经验。LeetCode-142 我之前栽在“第二阶段重置了 fast”这个坑上这个错误被记录为一个独立的笔记条目后来再遇到类似的双指针追及问题我会特意检查“重置指针时是否只重置了其中一个”。做题保持连续性的价值在这些细节里体现出来。到了 day135 还能翻出之前的错误记录对照着看进步是可感知的。写在最后的一点个人体会很多人觉得 LeetCode-142 只是一道普通的“中等题”但我觉得它是链表双指针问题的分水岭。能把这道题讲明白的人对“相遇”“追及”“距离差”这些概念的掌握程度都不会差。对我个人而言做这道题最大的收获不是记住了一个模板而是通过数学推导真正理解了快慢指针背后的逻辑后面再做寻找重复数、链表中间节点之类的题目思路都顺了很多。如果让我给一个刷题建议那就是不要满足于代码通过。花二十分钟把a (k - 1)L c的推导亲手写一遍比重复刷五道简单题都有用。这套推导写熟了以后遇到任何需要找环入口的变种题你都能从第一步开始从容分析。