环形链表Ⅱ这道题在力扣hot100里排得挺靠前也是我刷了这么多年题之后依然觉得“有点东西”的一道。你别看它只是个中等难度的链表题真正能在白板上把原理讲清楚、把代码一次写对的人比例远没有想象中高。很多朋友背下了“快慢指针相遇后再来一个指针从头走俩指针同步走相遇点就是环入口”这个结论但被面试官追问一句“为什么”就卡住了。这篇博文我就把这题的来龙去脉、数学推导、常见坑位、刷题位置全部拆开讲透争取让你看完之后不光能做对还能给别人讲明白。这道题适合谁正在啃hot100准备面试的同学、链表基础不牢需要补漏洞的新手、以及想把快慢指针这类“双指针技巧”吃透的人。你不需要有多深的算法底子只要会链表的遍历和基本的数学变换就能完全跟下来。1. 读懂题目从“判环”到“找入口”的思维升级1.1 一道题卡住一半人的原因环形链表Ⅱ的题目描述很简短给你一个链表的头节点 head返回链表开始入环的第一个节点如果链表无环则返回 null。听起来和环形链表Ⅰ很像但Ⅰ只要求你判断有没有环Ⅱ要求你把环的入口指出来。就是这一点变化让难度上了一个台阶。很多人在第一步就进了误区想当然地认为“找到快慢指针相遇的节点那不就是入口吗”不是。快慢指针在环里相遇的位置取决于环的周长和入环前那段链路的长度它是一个会漂移的节点只有在极特殊的链表结构下才会恰好等于入口节点。所以这题的核心不是“找到环里的某个节点”而是“根据相遇点反推出入口的位置”。这种“从结果反推起点”的思维和链表题里常见的“双指针找倒数第k个节点”“相交链表找交点”都不一样。那些题是顺着链表结构往前推就行这题需要你先跑出一个结果再做一次数学变换才能定位最终目标。这也是我认为它值得被选进hot100的原因——它考察的不是单纯coding能力而是把物理过程抽象成数学模型的能力。1.2 先想暴力解哈希表为什么能行我们先把最简单的方案讲清楚不是为了让你用它而是为了后续理解快慢指针的优势。哈希表法的思路特别朴素从 head 开始遍历链表每经过一个节点就检查这个节点是否已经出现在哈希集合里。如果出现过那这个节点就是环的入口如果遍历到 null 都每个节点只出现一次说明链表没有环。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)。从时间复杂度上看它已经完全达标了但空间上多了整个哈希表的开销。在很多面试场景里面试官会紧接着追问一句“能不能做到 O(1) 空间复杂度”这就是快慢指针登场的时机。这道题在hot100里的定位恰恰就是考察你是否掌握了“空间换时间”的反面——用更巧妙的数学关系把空间复杂度从 O(n) 压到 O(1)。所以我一直建议刷这道题的人别急着看快慢指针的解法先自己写一遍哈希表的版本一是确认你确实理解了题目本身二是写完之后你能直观感受到“还有没有更优的思路”这样后面的推导你才会有代入感。2. 快慢指针面试官想看到的解法2.1 判环的思路快指针终究会追上慢指针快慢指针判环的基本原理你用日常经验就能理解。想象两个人在环形跑道上跑步一个人速度快一个人速度慢只要跑道是环形的速度快的人迟早会从后面追上速度慢的人。在链表里落地这个思路就是用两个指针同时从 head 出发慢指针 slow 每次走一步快指针 fast 每次走两步。如果链表没有环fast 会先走到 null循环结束如果链表有环fast 和 slow 一定会在环里的某个位置相遇。为什么这样一定能遇上严谨一点说当 slow 进入环的时候fast 已经先一步在环里了。之后每过一轮移动slow 往前走一步fast 往前走两步fast 相对于 slow 而言每一轮靠近一步。既然是环形轨道距离是“有限”的所以最多走完一整圈fast 必然追上 slow。这个关系在环形链表Ⅰ里已经验证过了而且时间复杂度稳定在 O(n)。这里有一个细节值得注意fast 每次走两步会不会“跳过去”导致永远追不上 slow不会。因为二者的相对速度是每一步追赶一步而不是交替跨越。用数学语言说环上的每个节点在每一轮状态变化中fast 和 slow 的间距只会单调递减不会出现从“差一步”直接变成“差整整一圈”的情况。这也是为什么快慢指针判环的正确性是有理论保证的而不是“碰巧能行”。2.2 找入口的直觉想法相遇点到底有什么用现在我们已经能判断链表有环但题目要的是环的入口。直观上我们掌握的信息只有两个一个是链表的起点 head一个是在环里某处相遇的节点 meet。怎么从这两个信息里求出入口我先说一个直觉类比再上严谨推导。你站在链表的起点一个朋友站在环里的相遇点你们俩速度相同都每次走一步同时出发。奇妙的事情是你们最终会在环的入口处碰头。这个结论听起来有点反直觉因为从起点到入口的距离和从相遇点到入口的距离看起来没有任何关系。但当你把快指针在环里多跑的那些圈数算进去之后会发现两者在“模环长”的意义下是完全同余的。这个“模环长同余”的概念是后面一切推导的核心。你先在脑子里留一个印象快指针跑过的路除了和慢指针共同走过的那段之外剩下的就是在环里绕的整数圈。环上绕整数圈不改变相对位置所以它能提供一个等量关系把起点到入口这段路和相遇点到入口这段路联系起来。下面我们就开始正式推导。3. 核心推导为什么“再走一步”就能相遇在入口3.1 路程关系的严谨推导我们先约定三个变量后面所有公式都围绕它们展开。设链表头 head 到环入口节点的距离为 a环入口节点沿前进方向到快慢指针相遇节点的距离为 b相遇节点继续沿前进方向回到环入口节点的距离为 c。那么环的周长 L b c。慢指针从 head 出发到相遇点一共走过的路程是 a b。快指针从 head 出发到相遇点走过的路程是 a b nL其中 n 是快指针在环内比慢指针多绕的圈数n 取正整数。因为快指针的速度是慢指针的 2 倍所以在相同运动时间内快指针的路程等于慢指针路程的 2 倍于是有2(a b) a b nL化简一下a b nLa nL - b把 L b c 代入a n(b c) - ba (n - 1)(b c) c这个公式是整个算法的灵魂。它的含义是从头节点走到环入口的距离 a等于从相遇点出发先走向环入口的距离 c再在环里绕 (n - 1) 圈。而绕整圈数不会改变你在环上的位置所以我们可以说一个指针从 head 出发走 a 步能到环入口另一个指针从相遇点出发走 a 步同样也能到环入口。注意后半句说的是“走了 a 步之后到环入口”而不是“走 c 步就到”。很多文章把结论简单写成“a c”那是不严谨的只在 n 1 的特殊情况下才成立。在通用情况下正确的关系是 a (n - 1)L c。也就是说从相遇点出发走 a 步相当于先走完从相遇点到入口的那一段 c再绕上若干整圈。因为整圈不改变位置所以最终落在环入口上。3.2 关于 a c 的经典误解必须掰扯清楚“快慢指针相遇后一个指针从头走一个指针从相遇点走他们相遇在入口”——这个操作大家都会写但很多人在解释原理时说“因为 a c”这就不对了。我为啥要专门拿出一个小节讲这个误解因为我在面试别人和被人面试的时候都遇到过这种“结论背得滚瓜烂熟原理一推就倒”的情况。问题出在哪里呢假设链表头到入口很长有 100 个节点环很小周长只有 5 个节点。快指针在追上慢指针之前已经在环里绕了好多圈。这种情况下相遇点到入口的距离 c 不可能等于 a。但算法依然成立靠的是“绕整圈回到原位置”这个性质。如果面试官顺着你的错误解释追问一句“那如果 a 不等于 c你凭什么说它们会在入口碰上”你就很难自圆其说了。所以正确理解是从相遇点出发的指针走了 a 步之后在环上的位置是“相遇点 a 步”。代入前面推导的 a nL - b这个位置等于“相遇点 nL - b 步”。因为 nL 是整圈数可以忽略就等价于“相遇点 - b 步”。相遇点是从入口沿着前进方向走了 b 步到的地方那么“相遇点再往前走 nL - b 步”换算下来正好回到入口。这里的 nL 起了“容忍误差”的作用它把起点到入口的路程与相遇点到入口的路程对齐到了同一个模 L 的余数类里。3.3 同余视角的终极理解如果你有接触过数论里的同余概念这道题可以一句话总结从起点到入口的距离 a 和从相遇点到入口的距离 c在模环长 L 的意义下同余。写成数学符号就是 a ≡ c (mod L)。这比死记“a c”准确得多也通用得多。用同余视角再看整个算法的第二步slow 保持在相遇点不动新建一个指针 ptr 从 head 出发两指针每次都走一步。当 ptr 走了 a 步到达入口时slow 从相遇点也走了 a 步。根据上面推导slow 走 a 步之后必然落在入口于是两者在入口相遇。整个过程的每一步都是确定性的不存在“随机碰上”的可能。这也是我刷题这么多年的一个体会很多双指针题目的底层都是数学关系快慢指针只是把数学关系“翻译”成了链表上的移动。如果不能理解这层数学题目稍微变个花样比如让你求环的长度你就容易傻眼理解了数学你再去看任何讲解快慢指针的文章都会觉得它们讲的其实是同一件事。4. 代码实现Java与Python双版本4.1 Java实现与细节解析理论推导完成之后代码反而变得非常简单。核心就两步第一步用快慢指针找相遇点第二步一个指针从 head 出发一个指针从相遇点出发同步前进相遇处就是环入口。public class Solution { public ListNode detectCycle(ListNode head) { if (head null || head.next null) { return null; } ListNode slow head; ListNode fast head; boolean hasCycle false; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { hasCycle true; break; } } if (!hasCycle) { return null; } ListNode ptr head; while (ptr ! slow) { ptr ptr.next; slow slow.next; } return ptr; } }有几个细节值得说。初始时 slow 和 fast 都指向 head这是最推荐的写法因为这样推导里的路程关系成立。有些写法会让 fast 先走一步指向 head.next判环没问题但第二步的相遇位置和推导公式就对不上了容易给自己挖坑。while 循环的条件要写成 fast ! null fast.next ! null因为 fast 每次走两步如果 fast.next 为 null再取 fast.next.next 就会空指针。链表长度为 1 或 0 的时候直接返回 null 即可这个提前判断能让代码更清晰。我在实际刷题时习惯用 hasCycle 布尔变量记录是否有环而不是在循环里写两个 return。这样逻辑更线性也方便同学阅读。当然你完全可以在循环里判断相遇后直接进入第二步但那样代码的跳跃感会强一些面试时容易漏掉分支。4.2 Python实现与防御性写法Python 版本写起来更短但需要注意的细节是一样的。class Solution: def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]: if not head or not head.next: return None slow head fast head has_cycle False while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: has_cycle True break if not has_cycle: return None ptr head while ptr is not slow: ptr ptr.next slow slow.next return ptrPython 里判断节点是否相等建议用 is 而不是 。ListNode 没有重写eq用 比较的是对象的默认地址比较和 is 效果一样但语义上 is 更明确也避免了以后有人在 ListNode 里重写 equals 导致比较逻辑变化。另一个细节是类型注解 Optional[ListNode]这个在力扣环境里能通过在本地写的时候需要 from typing import Optional力扣的在线编辑器已经默认包含不用额外导入。防御性写法的意义在于你写的代码不只是为了通过这道题的测试用例而是要在面试里经得起追问。当面试官说“改成环入口前有100个节点的情况试试”你不需要改任何代码因为推倒过程本来就是通用的。4.3 边界条件与测试用例设计边界条件这块我多说几句因为面试官特别爱从这里下手。常见的有三类链表为空、链表只有一个节点、链表是首尾相接的完整环。链表为空和只有一个节点的情况代码开头直接返回 null没毛病。链表是完整环的情况很值得测假设链表只有一个节点并且这个节点的 next 指向自己那么 head 就是入口。上面的代码里head.next 等于 head不算 null所以不会提前 return。进入循环后slow 和 fast 都从 head 出发slow 走一步回到 headfast 走两步也回到 head第一步就相遇了。has_cycle 为 true然后 ptr head第二个 while 循环 ptr is slow 立即为真返回 head。结果是正确的。另一个有趣的边界是环特别大的情况比如链表有 10000 个节点其中最后 9999 个组成环。快慢指针会遇到很多次“貌似要相遇”的节点但因为相对速度恒定最终一定能在 O(n) 时间内相遇不会退化成 O(n^2)。这一点很多人担心实际上快慢指针的总步数是线性级别的原因在于相遇条件的数学保证不依赖碰运气。5. 刷题现场实录我踩过的坑与排查技巧5.1 如何手工构造有环链表来验证代码力扣的测试环境里它内部会把链表构造好再调用你的方法你只需要处理返回的节点。但我在本地调试的时候经常遇到一个问题怎么亲手造一个带环的链表这里分享一个我常用的构造方法。假设我想构造一个链表从 head 到入口有 3 个节点环的周长是 4 个节点。我先创建 7 个节点 n0 到 n6依次连接形成一条直线n0-n1-n2-n3-n4-n5-n6-null然后令 n6.next n3这样就得到一个环入口节点是 n3。调用 detectCycle(n0)期望返回 n3。验证的时候可以直接打印函数返回节点的 val看看是不是 3。这种构造方式能帮你在本地快速验证多种形态比如入口就是 head构造方法是让链表的尾节点 next 指向 head再比如环特别小让尾节点 next 指向自身再比如没有环那就保持普通的单链表。每改一次结构你都能直观看到算法的行为比干看推导有用得多。5.2 死循环与空指针问题排查我在帮朋友看代码时发现最常见的bug是 while 循环的条件写错。比如有的朋友写成 while fast.next ! null fast.next.next ! null当 fast 本身为 null 时先执行 fast.next 就直接空指针了。这个顺序不能反必须先判断 fast ! null再判断 fast.next ! null。还有一种情况是忘记更新指针导致死循环。比如在找相遇点的循环里只写了 slow slow.next忘写 fast fast.next.next快指针永远不动如果链表有环slow 会在环里无限转圈。排查的方法也很简单在循环体开头打印 slow.val 和 fast.val一旦发现某一方的值始终不变基本上就是漏了更新。另一个让人困惑的问题是“为什么我返回的节点老是入口的下一个节点”。这通常是因为第二步循环的初始条件设置错了。第二步开始时ptr 要从 head 出发slow 保持在相遇点。如果你不小心把 ptr 也设置成了 slow或者把 slow 重置为 head整个对应关系就乱了。解决方法是保持 slow 不动新建一个临时指针 ptr 从 head 开始这样逻辑上最清晰。5.3 不要背题要背推导这句话我说给每一个准备面试的人环形链表Ⅱ属于那种“背代码很容易讲道理很难”的题。如果你只是背下了最终代码面试官换一个问法比如问“如果快指针一次走三步算法还成立吗”你就会被问住。事实上快指针一次走三步时判环部分仍然可能工作但第二步的相遇点推导公式会变得完全不一样因为路程不再满足倍速关系。这个问题本身就是个很好的思维实验它能检验你是真懂还是假懂。我建议你学完这篇文章之后自己推导一遍快指针走三步的情况看能不能得出一个类似的递推关系。多余的思考不会浪费你的时间反而会帮你把同余思想彻底内化。这里我也放一个总结性的排查速查表方便你写代码时对照检查。症状可能原因解决方法空指针异常循环条件未判断 fast 或 fast.next改为 while (fast ! null fast.next ! null)死循环快指针未更新或更新错误检查 fast fast.next.next 那行是否缺失返回节点总是入口的下一个第二步 ptr 起点错误确保 ptr 从 head 出发slow 保持在相遇点无环链表返回了某个节点哈希表方案中对象比较错误用引用比较而不是值比较完整环时返回 null提前退出条件多写了 head.next null完整环时 head.next 不为 null无需提前返回6. 它在hot100里的“位置感”如何安排刷题顺序6.1 前置基础题一定要刷先我观察到一个现象很多读者直接刷hot100刷到环形链表Ⅱ时卡住了回头才发现自己环形链表Ⅰ都没做过甚至链表的快慢指针都没写过。这其实暴露了一个问题——刷题顺序如果太跳跃效率反而低。环形链表Ⅱ的前置知识主要是两样一是单链表的基本遍历和指针操作二是链表判环的快慢指针写法。如果你想找一组搭配的前置题目我的建议是先做环形链表Ⅰ再做相交链表最后再上环形链表Ⅱ。环形链表Ⅰ让你熟练掌握判环相交链表让你体会“两个指针同步走最终碰上”的技巧环形链表Ⅱ则在这个基础上加了一层数学推导。这个路径走下来每一道题都在为下一道题铺路不会出现知识点断层。6.2 同思路延伸题做一道顶五道掌握了环形链表Ⅱ的同余推导你能顺便解决的好几类变体题。比如“求环的长度”你可以在找到相遇点之后让一个指针原地不动另一个指针每次走一步再次回到相遇点时走过的步数就是环长。这个做法的原理就是前面说的“整圈回到原位置”。再比如“找到链表中倒数第k个节点”虽然不涉及环但用快慢指针让快指针先走k步的思路和环形链表Ⅱ里“两个指针以同速出发”的思想是相通的。hot100里还有不少题和这题共用类似的方法论。例如重排链表、删除链表的倒数第N个结点、回文链表它们本质上都是不同场景下的双指针应用。你如果能把环形链表Ⅱ的“物理直觉—数学建模—代码落地”这套方法论迁移过去刷题效率会高很多。我自己的习惯是每做完一道有代表性的链表题就把它归类到自己的笔记里标注它用到的核心技巧、和其他题的关联、踩过的坑。等刷完一个专题回头看笔记会发现原来整个专题的解法就那么几个套路。环形链表Ⅱ属于“快慢指针找位置”这个套路里最值得精做的一道因为它把套路背后的数学原理讲得最透彻。6.3 时间与空间复杂度在面试中的表述最后说一下面试时的表述。这题的快慢指针解法时间复杂度是 O(n)空间复杂度是 O(1)。这个 O(n) 的分析理由要能说清楚slow 每走一步fast 走两步在无环部分fast 先走完进入环后slow 最多再走不到一圈就会被 fast 追上所以总步数不超过链表节点数的常数倍。面试的时候建议把这个复杂度分析放在代码写完之后的解释环节不要一上来就说。顺序一般是先讲思路再写代码然后主动说出复杂度同时解释为什么是 O(n)。如果你能在解释完复杂度之后顺带提一句“相比哈希表方案这个做法的优势是空间 O(1)代价是需要多一步数学推导”面试官通常会点头认可因为这显示出你不只会写代码还懂方案取舍。空间复杂度是 O(1)意味着我们除了几个指针变量外没有额外分配和链表规模相关的存储空间。这里有一个小巧思第二个 while 循环里用的 ptr 和 slow 都是已有指针没有创建新链表也没有存节点集合所以空间是常数级的。这个点千万不要答错因为我见过有同学把返回的节点本身也算进空间复杂度里那是概念混淆。说实话这道题我在不同阶段刷过好几遍。第一次刷的时候我看完题解似懂非懂代码能过但讲不出原理。第二次刷我重新推导了公式才发现自己之前理解的“a c”是错的真正的核心是“模环长同余”。第三次刷我开始尝试给朋友讲这道题发现“讲出来”和“做出来”完全是两码事每一次讲述都会逼着你把模糊的地方解释清楚。所以如果你想把它真正吃透我给你的最后一个建议是找一个没做过这道题的朋友把你今天学到的推导过程讲给他听。如果在讲的过程中你卡壳了那卡壳的地方就是你需要回去重新理解的地方。技术分享的尽头不是代码是你能不能用最简单的话让另一个人也听懂。
环形链表Ⅱ全解：快慢指针原理推导与环入口定位实战
环形链表Ⅱ这道题在力扣hot100里排得挺靠前也是我刷了这么多年题之后依然觉得“有点东西”的一道。你别看它只是个中等难度的链表题真正能在白板上把原理讲清楚、把代码一次写对的人比例远没有想象中高。很多朋友背下了“快慢指针相遇后再来一个指针从头走俩指针同步走相遇点就是环入口”这个结论但被面试官追问一句“为什么”就卡住了。这篇博文我就把这题的来龙去脉、数学推导、常见坑位、刷题位置全部拆开讲透争取让你看完之后不光能做对还能给别人讲明白。这道题适合谁正在啃hot100准备面试的同学、链表基础不牢需要补漏洞的新手、以及想把快慢指针这类“双指针技巧”吃透的人。你不需要有多深的算法底子只要会链表的遍历和基本的数学变换就能完全跟下来。1. 读懂题目从“判环”到“找入口”的思维升级1.1 一道题卡住一半人的原因环形链表Ⅱ的题目描述很简短给你一个链表的头节点 head返回链表开始入环的第一个节点如果链表无环则返回 null。听起来和环形链表Ⅰ很像但Ⅰ只要求你判断有没有环Ⅱ要求你把环的入口指出来。就是这一点变化让难度上了一个台阶。很多人在第一步就进了误区想当然地认为“找到快慢指针相遇的节点那不就是入口吗”不是。快慢指针在环里相遇的位置取决于环的周长和入环前那段链路的长度它是一个会漂移的节点只有在极特殊的链表结构下才会恰好等于入口节点。所以这题的核心不是“找到环里的某个节点”而是“根据相遇点反推出入口的位置”。这种“从结果反推起点”的思维和链表题里常见的“双指针找倒数第k个节点”“相交链表找交点”都不一样。那些题是顺着链表结构往前推就行这题需要你先跑出一个结果再做一次数学变换才能定位最终目标。这也是我认为它值得被选进hot100的原因——它考察的不是单纯coding能力而是把物理过程抽象成数学模型的能力。1.2 先想暴力解哈希表为什么能行我们先把最简单的方案讲清楚不是为了让你用它而是为了后续理解快慢指针的优势。哈希表法的思路特别朴素从 head 开始遍历链表每经过一个节点就检查这个节点是否已经出现在哈希集合里。如果出现过那这个节点就是环的入口如果遍历到 null 都每个节点只出现一次说明链表没有环。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)。从时间复杂度上看它已经完全达标了但空间上多了整个哈希表的开销。在很多面试场景里面试官会紧接着追问一句“能不能做到 O(1) 空间复杂度”这就是快慢指针登场的时机。这道题在hot100里的定位恰恰就是考察你是否掌握了“空间换时间”的反面——用更巧妙的数学关系把空间复杂度从 O(n) 压到 O(1)。所以我一直建议刷这道题的人别急着看快慢指针的解法先自己写一遍哈希表的版本一是确认你确实理解了题目本身二是写完之后你能直观感受到“还有没有更优的思路”这样后面的推导你才会有代入感。2. 快慢指针面试官想看到的解法2.1 判环的思路快指针终究会追上慢指针快慢指针判环的基本原理你用日常经验就能理解。想象两个人在环形跑道上跑步一个人速度快一个人速度慢只要跑道是环形的速度快的人迟早会从后面追上速度慢的人。在链表里落地这个思路就是用两个指针同时从 head 出发慢指针 slow 每次走一步快指针 fast 每次走两步。如果链表没有环fast 会先走到 null循环结束如果链表有环fast 和 slow 一定会在环里的某个位置相遇。为什么这样一定能遇上严谨一点说当 slow 进入环的时候fast 已经先一步在环里了。之后每过一轮移动slow 往前走一步fast 往前走两步fast 相对于 slow 而言每一轮靠近一步。既然是环形轨道距离是“有限”的所以最多走完一整圈fast 必然追上 slow。这个关系在环形链表Ⅰ里已经验证过了而且时间复杂度稳定在 O(n)。这里有一个细节值得注意fast 每次走两步会不会“跳过去”导致永远追不上 slow不会。因为二者的相对速度是每一步追赶一步而不是交替跨越。用数学语言说环上的每个节点在每一轮状态变化中fast 和 slow 的间距只会单调递减不会出现从“差一步”直接变成“差整整一圈”的情况。这也是为什么快慢指针判环的正确性是有理论保证的而不是“碰巧能行”。2.2 找入口的直觉想法相遇点到底有什么用现在我们已经能判断链表有环但题目要的是环的入口。直观上我们掌握的信息只有两个一个是链表的起点 head一个是在环里某处相遇的节点 meet。怎么从这两个信息里求出入口我先说一个直觉类比再上严谨推导。你站在链表的起点一个朋友站在环里的相遇点你们俩速度相同都每次走一步同时出发。奇妙的事情是你们最终会在环的入口处碰头。这个结论听起来有点反直觉因为从起点到入口的距离和从相遇点到入口的距离看起来没有任何关系。但当你把快指针在环里多跑的那些圈数算进去之后会发现两者在“模环长”的意义下是完全同余的。这个“模环长同余”的概念是后面一切推导的核心。你先在脑子里留一个印象快指针跑过的路除了和慢指针共同走过的那段之外剩下的就是在环里绕的整数圈。环上绕整数圈不改变相对位置所以它能提供一个等量关系把起点到入口这段路和相遇点到入口这段路联系起来。下面我们就开始正式推导。3. 核心推导为什么“再走一步”就能相遇在入口3.1 路程关系的严谨推导我们先约定三个变量后面所有公式都围绕它们展开。设链表头 head 到环入口节点的距离为 a环入口节点沿前进方向到快慢指针相遇节点的距离为 b相遇节点继续沿前进方向回到环入口节点的距离为 c。那么环的周长 L b c。慢指针从 head 出发到相遇点一共走过的路程是 a b。快指针从 head 出发到相遇点走过的路程是 a b nL其中 n 是快指针在环内比慢指针多绕的圈数n 取正整数。因为快指针的速度是慢指针的 2 倍所以在相同运动时间内快指针的路程等于慢指针路程的 2 倍于是有2(a b) a b nL化简一下a b nLa nL - b把 L b c 代入a n(b c) - ba (n - 1)(b c) c这个公式是整个算法的灵魂。它的含义是从头节点走到环入口的距离 a等于从相遇点出发先走向环入口的距离 c再在环里绕 (n - 1) 圈。而绕整圈数不会改变你在环上的位置所以我们可以说一个指针从 head 出发走 a 步能到环入口另一个指针从相遇点出发走 a 步同样也能到环入口。注意后半句说的是“走了 a 步之后到环入口”而不是“走 c 步就到”。很多文章把结论简单写成“a c”那是不严谨的只在 n 1 的特殊情况下才成立。在通用情况下正确的关系是 a (n - 1)L c。也就是说从相遇点出发走 a 步相当于先走完从相遇点到入口的那一段 c再绕上若干整圈。因为整圈不改变位置所以最终落在环入口上。3.2 关于 a c 的经典误解必须掰扯清楚“快慢指针相遇后一个指针从头走一个指针从相遇点走他们相遇在入口”——这个操作大家都会写但很多人在解释原理时说“因为 a c”这就不对了。我为啥要专门拿出一个小节讲这个误解因为我在面试别人和被人面试的时候都遇到过这种“结论背得滚瓜烂熟原理一推就倒”的情况。问题出在哪里呢假设链表头到入口很长有 100 个节点环很小周长只有 5 个节点。快指针在追上慢指针之前已经在环里绕了好多圈。这种情况下相遇点到入口的距离 c 不可能等于 a。但算法依然成立靠的是“绕整圈回到原位置”这个性质。如果面试官顺着你的错误解释追问一句“那如果 a 不等于 c你凭什么说它们会在入口碰上”你就很难自圆其说了。所以正确理解是从相遇点出发的指针走了 a 步之后在环上的位置是“相遇点 a 步”。代入前面推导的 a nL - b这个位置等于“相遇点 nL - b 步”。因为 nL 是整圈数可以忽略就等价于“相遇点 - b 步”。相遇点是从入口沿着前进方向走了 b 步到的地方那么“相遇点再往前走 nL - b 步”换算下来正好回到入口。这里的 nL 起了“容忍误差”的作用它把起点到入口的路程与相遇点到入口的路程对齐到了同一个模 L 的余数类里。3.3 同余视角的终极理解如果你有接触过数论里的同余概念这道题可以一句话总结从起点到入口的距离 a 和从相遇点到入口的距离 c在模环长 L 的意义下同余。写成数学符号就是 a ≡ c (mod L)。这比死记“a c”准确得多也通用得多。用同余视角再看整个算法的第二步slow 保持在相遇点不动新建一个指针 ptr 从 head 出发两指针每次都走一步。当 ptr 走了 a 步到达入口时slow 从相遇点也走了 a 步。根据上面推导slow 走 a 步之后必然落在入口于是两者在入口相遇。整个过程的每一步都是确定性的不存在“随机碰上”的可能。这也是我刷题这么多年的一个体会很多双指针题目的底层都是数学关系快慢指针只是把数学关系“翻译”成了链表上的移动。如果不能理解这层数学题目稍微变个花样比如让你求环的长度你就容易傻眼理解了数学你再去看任何讲解快慢指针的文章都会觉得它们讲的其实是同一件事。4. 代码实现Java与Python双版本4.1 Java实现与细节解析理论推导完成之后代码反而变得非常简单。核心就两步第一步用快慢指针找相遇点第二步一个指针从 head 出发一个指针从相遇点出发同步前进相遇处就是环入口。public class Solution { public ListNode detectCycle(ListNode head) { if (head null || head.next null) { return null; } ListNode slow head; ListNode fast head; boolean hasCycle false; while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { hasCycle true; break; } } if (!hasCycle) { return null; } ListNode ptr head; while (ptr ! slow) { ptr ptr.next; slow slow.next; } return ptr; } }有几个细节值得说。初始时 slow 和 fast 都指向 head这是最推荐的写法因为这样推导里的路程关系成立。有些写法会让 fast 先走一步指向 head.next判环没问题但第二步的相遇位置和推导公式就对不上了容易给自己挖坑。while 循环的条件要写成 fast ! null fast.next ! null因为 fast 每次走两步如果 fast.next 为 null再取 fast.next.next 就会空指针。链表长度为 1 或 0 的时候直接返回 null 即可这个提前判断能让代码更清晰。我在实际刷题时习惯用 hasCycle 布尔变量记录是否有环而不是在循环里写两个 return。这样逻辑更线性也方便同学阅读。当然你完全可以在循环里判断相遇后直接进入第二步但那样代码的跳跃感会强一些面试时容易漏掉分支。4.2 Python实现与防御性写法Python 版本写起来更短但需要注意的细节是一样的。class Solution: def detectCycle(self, head: Optional[ListNode]) - Optional[ListNode]: if not head or not head.next: return None slow head fast head has_cycle False while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: has_cycle True break if not has_cycle: return None ptr head while ptr is not slow: ptr ptr.next slow slow.next return ptrPython 里判断节点是否相等建议用 is 而不是 。ListNode 没有重写eq用 比较的是对象的默认地址比较和 is 效果一样但语义上 is 更明确也避免了以后有人在 ListNode 里重写 equals 导致比较逻辑变化。另一个细节是类型注解 Optional[ListNode]这个在力扣环境里能通过在本地写的时候需要 from typing import Optional力扣的在线编辑器已经默认包含不用额外导入。防御性写法的意义在于你写的代码不只是为了通过这道题的测试用例而是要在面试里经得起追问。当面试官说“改成环入口前有100个节点的情况试试”你不需要改任何代码因为推倒过程本来就是通用的。4.3 边界条件与测试用例设计边界条件这块我多说几句因为面试官特别爱从这里下手。常见的有三类链表为空、链表只有一个节点、链表是首尾相接的完整环。链表为空和只有一个节点的情况代码开头直接返回 null没毛病。链表是完整环的情况很值得测假设链表只有一个节点并且这个节点的 next 指向自己那么 head 就是入口。上面的代码里head.next 等于 head不算 null所以不会提前 return。进入循环后slow 和 fast 都从 head 出发slow 走一步回到 headfast 走两步也回到 head第一步就相遇了。has_cycle 为 true然后 ptr head第二个 while 循环 ptr is slow 立即为真返回 head。结果是正确的。另一个有趣的边界是环特别大的情况比如链表有 10000 个节点其中最后 9999 个组成环。快慢指针会遇到很多次“貌似要相遇”的节点但因为相对速度恒定最终一定能在 O(n) 时间内相遇不会退化成 O(n^2)。这一点很多人担心实际上快慢指针的总步数是线性级别的原因在于相遇条件的数学保证不依赖碰运气。5. 刷题现场实录我踩过的坑与排查技巧5.1 如何手工构造有环链表来验证代码力扣的测试环境里它内部会把链表构造好再调用你的方法你只需要处理返回的节点。但我在本地调试的时候经常遇到一个问题怎么亲手造一个带环的链表这里分享一个我常用的构造方法。假设我想构造一个链表从 head 到入口有 3 个节点环的周长是 4 个节点。我先创建 7 个节点 n0 到 n6依次连接形成一条直线n0-n1-n2-n3-n4-n5-n6-null然后令 n6.next n3这样就得到一个环入口节点是 n3。调用 detectCycle(n0)期望返回 n3。验证的时候可以直接打印函数返回节点的 val看看是不是 3。这种构造方式能帮你在本地快速验证多种形态比如入口就是 head构造方法是让链表的尾节点 next 指向 head再比如环特别小让尾节点 next 指向自身再比如没有环那就保持普通的单链表。每改一次结构你都能直观看到算法的行为比干看推导有用得多。5.2 死循环与空指针问题排查我在帮朋友看代码时发现最常见的bug是 while 循环的条件写错。比如有的朋友写成 while fast.next ! null fast.next.next ! null当 fast 本身为 null 时先执行 fast.next 就直接空指针了。这个顺序不能反必须先判断 fast ! null再判断 fast.next ! null。还有一种情况是忘记更新指针导致死循环。比如在找相遇点的循环里只写了 slow slow.next忘写 fast fast.next.next快指针永远不动如果链表有环slow 会在环里无限转圈。排查的方法也很简单在循环体开头打印 slow.val 和 fast.val一旦发现某一方的值始终不变基本上就是漏了更新。另一个让人困惑的问题是“为什么我返回的节点老是入口的下一个节点”。这通常是因为第二步循环的初始条件设置错了。第二步开始时ptr 要从 head 出发slow 保持在相遇点。如果你不小心把 ptr 也设置成了 slow或者把 slow 重置为 head整个对应关系就乱了。解决方法是保持 slow 不动新建一个临时指针 ptr 从 head 开始这样逻辑上最清晰。5.3 不要背题要背推导这句话我说给每一个准备面试的人环形链表Ⅱ属于那种“背代码很容易讲道理很难”的题。如果你只是背下了最终代码面试官换一个问法比如问“如果快指针一次走三步算法还成立吗”你就会被问住。事实上快指针一次走三步时判环部分仍然可能工作但第二步的相遇点推导公式会变得完全不一样因为路程不再满足倍速关系。这个问题本身就是个很好的思维实验它能检验你是真懂还是假懂。我建议你学完这篇文章之后自己推导一遍快指针走三步的情况看能不能得出一个类似的递推关系。多余的思考不会浪费你的时间反而会帮你把同余思想彻底内化。这里我也放一个总结性的排查速查表方便你写代码时对照检查。症状可能原因解决方法空指针异常循环条件未判断 fast 或 fast.next改为 while (fast ! null fast.next ! null)死循环快指针未更新或更新错误检查 fast fast.next.next 那行是否缺失返回节点总是入口的下一个第二步 ptr 起点错误确保 ptr 从 head 出发slow 保持在相遇点无环链表返回了某个节点哈希表方案中对象比较错误用引用比较而不是值比较完整环时返回 null提前退出条件多写了 head.next null完整环时 head.next 不为 null无需提前返回6. 它在hot100里的“位置感”如何安排刷题顺序6.1 前置基础题一定要刷先我观察到一个现象很多读者直接刷hot100刷到环形链表Ⅱ时卡住了回头才发现自己环形链表Ⅰ都没做过甚至链表的快慢指针都没写过。这其实暴露了一个问题——刷题顺序如果太跳跃效率反而低。环形链表Ⅱ的前置知识主要是两样一是单链表的基本遍历和指针操作二是链表判环的快慢指针写法。如果你想找一组搭配的前置题目我的建议是先做环形链表Ⅰ再做相交链表最后再上环形链表Ⅱ。环形链表Ⅰ让你熟练掌握判环相交链表让你体会“两个指针同步走最终碰上”的技巧环形链表Ⅱ则在这个基础上加了一层数学推导。这个路径走下来每一道题都在为下一道题铺路不会出现知识点断层。6.2 同思路延伸题做一道顶五道掌握了环形链表Ⅱ的同余推导你能顺便解决的好几类变体题。比如“求环的长度”你可以在找到相遇点之后让一个指针原地不动另一个指针每次走一步再次回到相遇点时走过的步数就是环长。这个做法的原理就是前面说的“整圈回到原位置”。再比如“找到链表中倒数第k个节点”虽然不涉及环但用快慢指针让快指针先走k步的思路和环形链表Ⅱ里“两个指针以同速出发”的思想是相通的。hot100里还有不少题和这题共用类似的方法论。例如重排链表、删除链表的倒数第N个结点、回文链表它们本质上都是不同场景下的双指针应用。你如果能把环形链表Ⅱ的“物理直觉—数学建模—代码落地”这套方法论迁移过去刷题效率会高很多。我自己的习惯是每做完一道有代表性的链表题就把它归类到自己的笔记里标注它用到的核心技巧、和其他题的关联、踩过的坑。等刷完一个专题回头看笔记会发现原来整个专题的解法就那么几个套路。环形链表Ⅱ属于“快慢指针找位置”这个套路里最值得精做的一道因为它把套路背后的数学原理讲得最透彻。6.3 时间与空间复杂度在面试中的表述最后说一下面试时的表述。这题的快慢指针解法时间复杂度是 O(n)空间复杂度是 O(1)。这个 O(n) 的分析理由要能说清楚slow 每走一步fast 走两步在无环部分fast 先走完进入环后slow 最多再走不到一圈就会被 fast 追上所以总步数不超过链表节点数的常数倍。面试的时候建议把这个复杂度分析放在代码写完之后的解释环节不要一上来就说。顺序一般是先讲思路再写代码然后主动说出复杂度同时解释为什么是 O(n)。如果你能在解释完复杂度之后顺带提一句“相比哈希表方案这个做法的优势是空间 O(1)代价是需要多一步数学推导”面试官通常会点头认可因为这显示出你不只会写代码还懂方案取舍。空间复杂度是 O(1)意味着我们除了几个指针变量外没有额外分配和链表规模相关的存储空间。这里有一个小巧思第二个 while 循环里用的 ptr 和 slow 都是已有指针没有创建新链表也没有存节点集合所以空间是常数级的。这个点千万不要答错因为我见过有同学把返回的节点本身也算进空间复杂度里那是概念混淆。说实话这道题我在不同阶段刷过好几遍。第一次刷的时候我看完题解似懂非懂代码能过但讲不出原理。第二次刷我重新推导了公式才发现自己之前理解的“a c”是错的真正的核心是“模环长同余”。第三次刷我开始尝试给朋友讲这道题发现“讲出来”和“做出来”完全是两码事每一次讲述都会逼着你把模糊的地方解释清楚。所以如果你想把它真正吃透我给你的最后一个建议是找一个没做过这道题的朋友把你今天学到的推导过程讲给他听。如果在讲的过程中你卡壳了那卡壳的地方就是你需要回去重新理解的地方。技术分享的尽头不是代码是你能不能用最简单的话让另一个人也听懂。
