环形链表 II 这道题在链表相关的算法题里算是“绕不过去的一道坎”。LeetCode 第 142 题要求我们不仅判断链表有没有环还要精确找到“环的入口节点”。很多同学能看懂 141 题的判环写法但到了这一题快慢指针相遇之后的那套“再走一次”的操作往往只能靠背结论。这篇文章我想把那么“结论”背后的为什么彻底拆开从数学推导到代码实现再到面试现场怎么讲清楚一轮讲透。这道题真正解决的是在链表的尾节点指向了前面某个节点、形成闭环的场景下我们要把一个链表的完整形态还原出来定位出环起点。它适合三类人阅读第一类是准备技术面试、正在刷题的开发者第二类是理解了快慢指针判环、但对“求入口”的推导感到模糊的人第三类是准备给他人讲题、需要把思路梳理清楚的读者。无论你是哪种建议先弄明白一个核心点——这题的标准解法不是二分、不是动态规划而是 Floyd 判圈算法也就是快慢指针。1. 题面拆解为什么“找入口”比“判环”难一个量级1.1 题目要求与输入输出特征题目给的输入只有一个链表的头节点 head我们要返回的是“链表开始入环的第一个节点”。这里有个容易被忽略的边界条件如果链表没有环返回 null。举个最简单的例子。链表 A - B - C - D - B这里 B 就是入环点C、D 在环内D 的 next 指向 B。这个链表里存在环但环并不是从 head 开始的而是从中间的 B 节点开始。入环点就是那个“环内第一个节点”也就是说从 B 走下去会绕圈但 B 本身是环的一部分。再看一个容易混淆的例子。链表 head - A - B - C然后 C 指向 A。这个环的入口是 A而不是 head。很多初学者会把“相遇点”当成入口这是错误的。相遇点只是两个指针第一次碰面的位置它取决于快指针的绕圈次数和环的大小不一定等于入环点。所以题目的核心有三个动作确认链表中是否存在环、找到环的起点、处理无环情况。判断前后两个动作其实都可以复用思想但中间的“找到起点”是最考验推导能力的一环。1.2 从 141 题到 142 题的思路升级141 题只需要返回布尔值告诉我们有没有环。标准的做法是快慢指针同时从 head 出发慢指针每次走一步快指针每次走两步。如果链表中存在环那么快指针一定会在环内“追上”慢指针二者相遇。但在 142 题里仅仅判断是否相遇是不够的。我们需要在相遇之后继续利用某种几何关系把入环点“算”出来。这里很多人会卡住明明快慢指针已经相遇了然后呢为什么要把快指针重新放到 head然后两个指针同时以相同速度前进为什么它们再次相遇的位置就是入环点这背后是一个有趣且严谨的数学等式。只要把这个等式推导一遍以后再遇到这题就不需要背结论了。提示如果只是写题解很多文章会直接给出代码。但面试官真正想听到的是“你为什么敢在相遇后让快指针回到 head”。推导过程才是得分点。2. 先看最直白的方案哈希表记录法2.1 哈希表法的核心思路在引入 Floyd 判圈法之前我们先把哈希表法讲明白。它的思路非常直接从 head 开始遍历链表每经过一个节点就把节点的引用存入一个哈希集合中。如果当前节点已经在集合里说明这个节点就是环的入口直接返回它如果一直走到 null说明无环返回 null。为什么哈希表法在这里是正确的关键在于链表中每个节点都是内存中的独立对象即使两个节点的 val 相同它们在内存中的地址也不同引用不相等。用集合存引用而不是存值才能准确判重。以链表 A - B - C - D - B 为例遍历顺序是 A、B、C、D第五次回到 B。当检查第五个节点 B 时会发现 B 已经在集合中于是返回 B。这个过程非常直观不需要什么数学推导。2.2 哈希表法的代码实现与复杂度对应的代码大概是下面这个样子def detectCycle(head): visited set() cur head while cur: if cur in visited: return cur visited.add(cur) cur cur.next return None这段代码逻辑清晰看起来没什么问题。它的时间复杂度是 O(N)因为每个节点最多被访问一次空间复杂度是 O(N)因为我们需要额外的集合来存放所有已访问的节点。如果面试时你只写出这个版本面试官通常会追问一句能不能把空间复杂度优化到 O(1)所以才有了快慢指针法。换句话说哈希表法是一个用来验明思路的“地基”而快慢指针法才是这个题目的精华。2.3 哈希表法的局限性哈希表法的优点是容易理解几乎不可能写错。但它的缺陷也很明显当链表长度达到百万级额外使用一个哈希集合会占用可观的堆内存这在嵌入式、底层系统或内存受限的场景下是无法接受的。更重要的是哈希表法没有充分挖掘链表“指针指向”这个特性。链表结构里天然包含了后继信息我们完全可以利用数学上的追赶问题来求解而不是简单地把所有节点都记下来。3. Floyd 判圈法快慢指针如何把环“跑”出来3.1 快慢指针的基本设定Floyd 判圈算法来自循环检测思想它在链表题的出场率极高。标准做法初始化两个指针 slow 和 fast都指向 head。slow 每次移动一步fast 每次移动两步两个指针同时移动。如果链表无环那么 fast 会在某一刻到达 null 或者 fast.next 为 null此时循环结束返回 null。如果链表有环那么 fast 和 slow 最终会在环内的某个位置相遇。需要注意相遇的位置一定在环内不可能在环外。因为 slow 一旦进入环它就在环内绕圈fast 已经比 slow 早进入环也一定在环内绕圈二者最终会追上。这里有个常见疑问为什么快指针每次走两步而不是三步、四步从原理上说只要两个指针速度不同它们在环内就存在速度差最终一定能够相遇。但选择“两倍速”有两个好处最小且直观的速度差慢指针走 1 步快指针走 2 步相对速度为 1 步/单位时间最容易分析追及关系数学推导简洁后续求入环点时两倍速的关系会产生极其干净的等式。用生活化的例子来说这就像操场跑步。慢者在前面跑快者在后面追只要跑道是闭合的快者一定会追上慢者。关键在于追上时快者已经比慢者多跑了一段“完整的环长”的整数倍。3.2 第一次相遇的代码框架我们先写一个只负责“判环”的版本方便理解def hasCycle(head): if not head or not head.next: return False slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False注意这里 while 条件写的是fast and fast.next因为 fast 一次跳两步只有确保 fast 和 fast.next 都不为空才能安全地访问 fast.next.next。在 142 题中我们不是立刻返回 True而是要在相遇之后继续操作找出入口。于是代码结构会变成def detectCycle(head): if not head or not head.next: return None slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: fast head while slow is not fast: slow slow.next fast fast.next return slow return None这段代码前半段是标准的判环后半段是关键把 fast 重新指向 head然后两个指针都以每次一步的速度前进。它们再次相遇的位置就是环的入口。4. 最关键的数学推导为什么“再次相遇点 入环点”4.1 参数定义与符号约定为了把推导讲清楚我们先定义几个符号。假设环的入口节点为 P头节点 head 到 P 的距离为 a。也就是说从头节点出发移动 a 步到达环的入口节点。假设第一次相遇点也就是 slow 和 fast 第一次碰面的节点为 M。从 P 节点出发顺时针移动 b 步到达 M。注意这里的顺序是头节点 → 入口 → 相遇点。从 M 继续顺时针移动 c 步会再次回到入口节点 P。那么环的长度 L b c。同时我们用 n 表示从速度较快的那根指针开始进入环到它与慢指针第一次相遇为止快指针在环内绕的完整圈数。n 是一个大于等于 1 的整数。用一张简单的示意图帮助理解head --a步-- P(入口) --b步-- M(相遇点) ^ | | c步 | ------------实际上环的结构可以看作三段a 是入环前的直线部分b 是入口到相遇点的那段弧c 是相遇点回到入口的那段弧。4.2 两倍速关系带来的关键等式现在开始推时间。当第一次相遇发生时我们假设 slow 走过的总距离是 S。slow 从头节点出发直到相遇这个过程中它最多只在环内走了一段弧 b不会重复绕圈。为什么因为在 slow 进入环之后快指针已经领先它一截慢指针可能还没走完一圈两指针就已经相遇了。严谨地说在第一次相遇发生前slow 在环内走过的长度必然不超过一圈。如果等于一圈它会回到入口 P而这时 fast 也在环内绕了整圈二者在入口处相遇等价于 b0 的情况也是允许的。所以 S a b。快指针走过的距离是 F。由于 fast 的速度是 slow 的 2 倍所以相同时间内 F 2 * S 2 * (a b)。另一方面快指针的路径可以从结构上分析它先走完 a 到达入口 P然后进入环内绕圈。在第一次相遇前fast 在环内绕了 n 圈整再多走一段弧 b最终到达相遇点 M。因此F a n * (b c) b这里的 (b c) 就是整圈环长 L。把两个 F 的表达式联立2 * (a b) a n * (b c) b化简2a 2b a b n * (b c) a b n * (b c)这个等式就是整个算法的核心。它的左边是 slow 走过的距离右边是 n 倍的环长。它告诉我们从头节点到相遇点的这段距离恰好是环长的整数倍。继续变形目标是解出 aa n * (b c) - b a n * (b c) - b a (n - 1) * (b c) c这个式子非常漂亮。它表明从头节点走到入口的步数 a等于“从相遇点 M 走 c 步回到入口 P然后再绕 (n-1) 整圈”的总步数。4.3 推导结果与第二次遍历的对应关系有了上面的式子接下来就顺理成章了。我们把 fast 指针重新放回 head然后两个指针都每次走一步。当 slow 从 M 点出发走 c 步它会先回到入口 P此时 fast 从 head 出发走 c 步它到了什么位置由于 a c (n-1) * L所以 fast 走了 c 步之后距离入口节点还差 (n-1) 圈。也就是说fast 还没到入口。但我们已经知道两个指针速度相同起点不同它们最终会在某个时刻相遇。现在从 c 步之后继续走fast 还需要走 a - c 步即 (n-1)*L 步才能到达入口而 slow 也在同时从入口 P 出发绕 (n-1) 圈最终也回到入口 P。所以二者再次相遇的位置正是入口 P。这段路程中两个指针恰好都走了 a 步构成一次精确会合。用更通俗的话总结第二次遍历时一个指针从 head 出发另一个从第一次相遇点出发它们速度相同。因为距离 head 到入口的步数与相遇点走回入口的步数加上若干个整圈相等所以当第一个指针走到入口时第二个指针也一定回到入口。于是两点相遇。注意这里的“走 c 步”是借用推导过程实际上代码里让两个指针同时一步一步走即可不需要人为控制步数。它们自行会相遇。4.4 一个具体数字例子为了让这个推导不那么抽象来一个实例。假设链表是 head(H) - 1 - 2 - 3 - 4 - 2其中节点 2 是环的入口 P。那么a 2H 到节点 1再到节点 2共 2 步环长为 4节点 2、3、4、2假设 slow 与 fast 第一次相遇发生在节点 4即 M 节点 4那么从入口 2 到 M 节点 4b 22 走一步到 3再走一步到 4从 M 回入口c 24 走一步到 2正好入口代入式子 a (n-1)*L c得 2 (n-1)*4 2可以取 n1满足条件。第一次相遇时fast 从 head 出发走 a b 2 2 4 步就到 Mslow 走 2 步也到 M而此时 fast 在环内只跑了 1 圈加 b 段二者正好相遇。第二次遍历时fast 回到 headslow 留在 M。两个指针同时走一步slow 到 2入口fast 到 H.next节点 1。第二次走一步slow 到 3fast 到 2。第三次走一步slow 到 4fast 到 3。第四次走一步slow 到 2入口fast 到 4。第五次走一步slow 到 3fast 到 2。第六次slow 到 4fast 到 3。第七次slow 到 2fast 到 4……这看起来没有相遇等一下我上面这段推演方向弄错了需要重新纠正避免误导。通常如果 n1那么 c 应该等于 a。上述 a2、c2 满足。第二次遍历时两个指针都每次一步从不同位置出发。fast 从 headslow 从 M。因为 a c 且 n1fast 走 2 步到入口 2slow 从 M 出发走 2 步也到入口 2。它们会在第 2 步同时到达入口正好相遇。所以下一次相遇就在节点 2 处。但刚才我上面从 M 点出发的第一个步长方向应该按原链表 next 方向走M4 的 next 指向 2所以 slow 第一步到 2第二步到 3第三步到 4……这就不对。这里出了问题关键在于我的例子符号方向我说“从 M 回入口c2”通常“相遇点 M”是通过 next 方向继续前进回到入口那么 M.next 就是指回入口。但我的示例里 4.next 是 2所以 M 的 next 确实回到入口 2。走一步就到 2c 应该等于 1 而不是 2。所以例子不匹配。为了让推导自洽我们应该让 bc 构成环长。假设环入口是节点 1这样重新举例H - 1 - 2 - 3 - 1其中 1 是入口。a 1环长 L 3。如果 slow 和 fast 第一次相遇在节点 3从入口 1 出发走一步到 2走两步到 3所以 b2从 3 走一步回到 1所以 c1。代公式 a c (n-1)L 1 0 1n1成立。第二次遍历中fast 从 head 出发slow 从 M节点 3出发各走一步fast 到 1slow 从 3 的 next 到 1。两人立刻在入口 1 相遇。完美匹配。所以一定要保证例子里 c 的步数与 next 方向一致。我重新设计例子时就别东扯西扯。用这个 H-1-2-3-1 例子就好head 记为 H节点 1 的值是1也是入口。这样例子简洁a1b2c1L3n1。第一次相遇点在节点 3第二次两个指针各走 1 步在入口 1 相遇。4.5 为什么快指针在第一次相遇前一定只比慢指针多跑 n 整圈这个点经常被追问。设相遇前 fast 在环内绕了 n 圈整这是根据速度关系自然得出的。因为 F 2SF - S S也就是相遇时快指针比慢指针多走的距离恰好等于慢指针的总距离。慢指针的总距离是 ab而 ab 恰好是环长整数倍已经推导过所以快指针比慢指针多跑的距离就是整数圈。这样一来n 的取值为正整数且通常比实际绕圈数更有解释意义。在一个环中只要速度差大于零快指针最终一定能赶上慢指针这就是循环追及问题的核心。5. 代码实现与边界条件处理5.1 Python 完整实现把上面的推导落实到代码最终版本非常简短class ListNode: def __init__(self, x): self.val x self.next None def detectCycle(head): if not head or not head.next: return None slow head fast head # 第一阶段找到第一次相遇点 while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: break else: return None # 第二阶段重新定位入口 fast head while slow is not fast: slow slow.next fast fast.next return slow这里有个 Python 技巧while...else结构。如果循环正常结束说明 fast 或者 fast.next 变成了空代表无环执行return None如果触发了 break说明找到了相遇点跳过 else 块。第二阶段不需要判空因为已经确认链表有环。两个指针一定会在进入环之前或进入环的瞬间相遇不会出现某个指针为空的情况。5.2 Java 与 C 版本参考用 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; } fast head; while (slow ! fast) { slow slow.next; fast fast.next; } return slow; } }C 同理注意判空和指针比较class Solution { public: ListNode *detectCycle(ListNode *head) { if (head nullptr || head-next nullptr) { return nullptr; } ListNode *slow head; ListNode *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { break; } } if (fast nullptr || fast-next nullptr) { return nullptr; } fast head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; } };5.3 边界情况单节点、双节点、无环链表的处理边界情况是这类题最容易写错的地方空链表 head null直接返回 null单节点无环节点 next 为 null返回 null单节点自环head.next head第一阶段 slow 和 fast 都会在第一步走到同一位置慢指针走一步到 head快指针走两步也到 head相遇点就是入口 head双节点环1 - 2 - 1入口是 1第一次相遇点也是 1长链无环第一阶段正常遍历fast 先到 null返回 null。在写代码时最好把对 head 和 head.next 的空检查放在最前面避免访问空指针的 next。6. 手写链路推演三种典型结构全步骤演示6.1 结构一无环链表链表 H - A - B - C - null。slow 和 fast 都从 H 出发轮次slow 位置fast 位置状态1HH初始2AB未相遇3Bnullfast 为空无环代码会执行return None。6.2 结构二环在链表尾部链表 H - A - B - C - D - B。入口是 B环长是 3B、C、D。我们按次序推进轮次slow 位置fast 位置1HH2AC3BB已绕一圈稍等需要计算这里不能简单罗列我们还是严谨一点初始都在 H第一轮 slow 到 Afast 到 C第二轮 slow 到 Bfast 到 B第二轮slow 从 A 到 Bfast 从 C 到 D 再到 B实际上 fast 一步跳两个节点C.next 是 DD.next 是 B所以 fast 第二轮到 B。slow 第二轮到 B二者正好在 B 相遇。此时 B 恰好就是入口返回 B非常顺利。如果换成链表 H - A - B - C - D - E - C入口 C环长 3初始在 H第一轮 slow 到 Afast 到 Cfast 从 H 两步跳到 C这不可能因为 head 到 A 是 1 步到 B 是 2 步到 C 是 3 步。fast 第一步从 H 跳到 B等等快指针一次跳两步从 H 出发第一步到达 BH→AA→B不是 C。慢指针第一步到 A。第二轮 slow 到 Bfast 从 B 跳两步到 DB→CC→D。第三轮 slow 到 Cfast 从 D 跳两步到 BD→EE→CD.nextEE.nextC所以到 C不对D 到 C 是两步也就是这一轮 fast 到达 C所以相遇点就是 C入口 C。用公式验证a2H→A→C注意 head 到入口 C 是 3 步从 H 出发到 A 需要 1 步到 B 需要 2 步到 C 需要 3 步所以 a3。但是 slow 走到相遇点 C 需要 3 步fast 速度是 slow 两倍走了 6 步。环长 L3fast 进环前需要走 a 步也就是从 H 到 C 走了 3 步然后入环绕 1 圈又到 C相遇。所以 n1。第二次遍历时 fast 回 headslow 留在 C两边一步fast 到 Aslow 到 DC→D没相遇第二步fast 到 Bslow 到 E第三步fast 到 Cslow 到 C相遇正是入口 C。完美。这两个例子说明相遇点不一定是入口但第二次遍历一定会相遇在入口。6.3 结构三环在链表头部附近链表 H - A - B - A。入口是 A环长是 2A、B。初始 H。第一轮slow 到 Afast 到 B。第二轮slow 到 Bfast 从 B 跳一步到 A不对fast 每次两步从 B 跳两步B.nextAA.nextB所以 fast 回到 Bslow 到 B二者在 B 相遇。相遇点 B入口 A。然后 fast 回 head两个指针同时走第一步 fast 到 Aslow 从 B 走到 A立刻相遇返回 A。这三个典型结构覆盖了无环、环在末端、环在头部附近三种场景代码逻辑一致。7. 常见错误与面试考点深度复盘7.1 最容易犯的三种错误错误一判空条件写漏。在 while 中用fast.next.next时如果 fast 本身是 null程序会抛出空指针异常。所以必须写成while fast and fast.next不能图省事。错误二初始指针设置不同。有些同学让 slow 先走一步、fast 先走两步再进入循环这时要额外考虑初始位置的相遇判断容易漏判。统一从 head 出发使用前插式判断代码更干净。错误三第一次相遇后直接返回相遇节点。这是这道题最常见的错误。相遇点不是入口直接返回的话如果数据恰好凑巧相同可能掩盖问题但绝大多数情况下会得到错误答案。必须重新移动 fast 到 head再走一次。7.2 面试官追问清单面试官在这道题上常见的追问包括如果不能修改链表结构你怎么做用上面的方法就是答案它不修改链表结构证明快慢指针一定会相遇吗追及问题速度差存在且轨道闭合如果快指针每次走三步还能用同样的相遇推论求入口吗原则上仍能相遇但不能推出 a c (n-1)L 这个简单等式因此常规解法固定用两倍速不要自行改动如何求环的长度第一次相遇后保持其中一个指针不动另一个指针每次走一步统计再次回到相遇点所需步数就是环长在这些追问里最需要重视的是数学推导要讲清。不要光说“这是模板”而是把 a b n(b c) 写出来一边写一边解释含义。面试官真正看重的不是背诵能力而是逻辑链是否完整。7.3 与链表其他题目的横向关联142 题的解法思想还能迁移到其他题目。141 题只判环不输出入口是 142 的简化版。876 题“链表的中间节点”快慢指针快指针每次两步、慢指针每次一步快指针到尾时慢指针恰在中点属于同一思想的另一个应用。160 题“相交链表”一种经典解法是把其中一个链表的尾部接到另一个链表的头部转化成环形链表求入口用的就是 142 的思想。所以这道题不是孤立的“背结论题”。一旦吃透了 Floyd 判圈法再去解决链表类的追及问题会顺手很多。8. 复杂度对比与无额外空间的现实意义8.1 两种方案的时间与空间对比方案时间复杂度空间复杂度特点哈希表法O(N)O(N)思路简单代码短但额外空间开销大Floyd 判圈法O(N)O(1)需要推导数学关系面试最优解这里的时间复杂度需要说明两个指针整体移动次数与链表长度成正比如果链表很长且环很小快指针可能需要在环内绕比较多圈才相遇但总体仍在 O(N) 量级。具体到本题的朴素理解就是从 head 到入环点加上环内有限次绕圈不会超过线性次数太多。Floyd 判圈法 O(1) 空间意味着它可以在不额外占用内存的情况下处理上亿节点的链表在真实场景中比如内存管理、网络数据包检测、文件系统循环引用检测等方向这种不增加存储开销的算法非常有价值。8.2 实际工程中的抽象意义链表环检测不只是面试题。在操作系统或数据库的日志记录、依赖关系解析、编译器符号表处理中可能会遇到对象引用形成循环引用的问题。能判断是否存在环、找到环的起点就可以进一步做循环清除或异常定位。比如某个垃圾回收器在扫描对象引用图时需要识别循环引用就可能采用类似的快慢指针思想。当然实际工程里情况更复杂但核心的“标记-检测-定位”逻辑与 142 题一脉相承。9. 这道题后续还能怎么扩展我自己每年刷到这道题都会重新推一遍公式不是因为记不住而是每次推都能加深对“追及问题”的理解。个人建议不要满足于把代码 AC。可以尝试自己编不同结构的链表比如入口在第一个节点、入口在中间、入口在最后一个节点、环长只有 1 等手动按指针路径模拟一遍。这样再遇到变体题比如“求环中包含的节点数量”或“判断两个链表是否相交”你会更快找到办法。扩展玩法是把链表结构换成数组形式的“跳跃游戏”给定一个数组每个元素表示下一步跳到哪个下标判断是否存在循环以及循环的入口。本质上就是 142 题的数组版但它的解法依然可以用快慢指针思想只不过下标访问代替了指针访问。能把链表题迁移到数组场景说明你对 Floyd 判圈的掌握才真正到位。如果后续想深入建议一并刷完 141、876、160 三道题形成一套“快慢指针四连”。这几道题放在一起既能通过对比理解不同场景下的细节差异也能为二叉树、图里的循环检测打下基础。最后分享一个我实际用起来很顺的小办法讲这道题的时候别急着写代码先在白板上画一条带环的链表然后用笔模拟快慢指针的每一步。画完之后公式推导自然就有了。真正理解之后你根本不需要背答案。 
长河君 · 2026/10/18 10:46:32 · 阅读 1.2k 环形链表 II 详解：快慢指针寻找环入口的数学推导与实现
环形链表 II 这道题在链表相关的算法题里算是“绕不过去的一道坎”。LeetCode 第 142 题要求我们不仅判断链表有没有环还要精确找到“环的入口节点”。很多同学能看懂 141 题的判环写法但到了这一题快慢指针相遇之后的那套“再走一次”的操作往往只能靠背结论。这篇文章我想把那么“结论”背后的为什么彻底拆开从数学推导到代码实现再到面试现场怎么讲清楚一轮讲透。这道题真正解决的是在链表的尾节点指向了前面某个节点、形成闭环的场景下我们要把一个链表的完整形态还原出来定位出环起点。它适合三类人阅读第一类是准备技术面试、正在刷题的开发者第二类是理解了快慢指针判环、但对“求入口”的推导感到模糊的人第三类是准备给他人讲题、需要把思路梳理清楚的读者。无论你是哪种建议先弄明白一个核心点——这题的标准解法不是二分、不是动态规划而是 Floyd 判圈算法也就是快慢指针。1. 题面拆解为什么“找入口”比“判环”难一个量级1.1 题目要求与输入输出特征题目给的输入只有一个链表的头节点 head我们要返回的是“链表开始入环的第一个节点”。这里有个容易被忽略的边界条件如果链表没有环返回 null。举个最简单的例子。链表 A - B - C - D - B这里 B 就是入环点C、D 在环内D 的 next 指向 B。这个链表里存在环但环并不是从 head 开始的而是从中间的 B 节点开始。入环点就是那个“环内第一个节点”也就是说从 B 走下去会绕圈但 B 本身是环的一部分。再看一个容易混淆的例子。链表 head - A - B - C然后 C 指向 A。这个环的入口是 A而不是 head。很多初学者会把“相遇点”当成入口这是错误的。相遇点只是两个指针第一次碰面的位置它取决于快指针的绕圈次数和环的大小不一定等于入环点。所以题目的核心有三个动作确认链表中是否存在环、找到环的起点、处理无环情况。判断前后两个动作其实都可以复用思想但中间的“找到起点”是最考验推导能力的一环。1.2 从 141 题到 142 题的思路升级141 题只需要返回布尔值告诉我们有没有环。标准的做法是快慢指针同时从 head 出发慢指针每次走一步快指针每次走两步。如果链表中存在环那么快指针一定会在环内“追上”慢指针二者相遇。但在 142 题里仅仅判断是否相遇是不够的。我们需要在相遇之后继续利用某种几何关系把入环点“算”出来。这里很多人会卡住明明快慢指针已经相遇了然后呢为什么要把快指针重新放到 head然后两个指针同时以相同速度前进为什么它们再次相遇的位置就是入环点这背后是一个有趣且严谨的数学等式。只要把这个等式推导一遍以后再遇到这题就不需要背结论了。提示如果只是写题解很多文章会直接给出代码。但面试官真正想听到的是“你为什么敢在相遇后让快指针回到 head”。推导过程才是得分点。2. 先看最直白的方案哈希表记录法2.1 哈希表法的核心思路在引入 Floyd 判圈法之前我们先把哈希表法讲明白。它的思路非常直接从 head 开始遍历链表每经过一个节点就把节点的引用存入一个哈希集合中。如果当前节点已经在集合里说明这个节点就是环的入口直接返回它如果一直走到 null说明无环返回 null。为什么哈希表法在这里是正确的关键在于链表中每个节点都是内存中的独立对象即使两个节点的 val 相同它们在内存中的地址也不同引用不相等。用集合存引用而不是存值才能准确判重。以链表 A - B - C - D - B 为例遍历顺序是 A、B、C、D第五次回到 B。当检查第五个节点 B 时会发现 B 已经在集合中于是返回 B。这个过程非常直观不需要什么数学推导。2.2 哈希表法的代码实现与复杂度对应的代码大概是下面这个样子def detectCycle(head): visited set() cur head while cur: if cur in visited: return cur visited.add(cur) cur cur.next return None这段代码逻辑清晰看起来没什么问题。它的时间复杂度是 O(N)因为每个节点最多被访问一次空间复杂度是 O(N)因为我们需要额外的集合来存放所有已访问的节点。如果面试时你只写出这个版本面试官通常会追问一句能不能把空间复杂度优化到 O(1)所以才有了快慢指针法。换句话说哈希表法是一个用来验明思路的“地基”而快慢指针法才是这个题目的精华。2.3 哈希表法的局限性哈希表法的优点是容易理解几乎不可能写错。但它的缺陷也很明显当链表长度达到百万级额外使用一个哈希集合会占用可观的堆内存这在嵌入式、底层系统或内存受限的场景下是无法接受的。更重要的是哈希表法没有充分挖掘链表“指针指向”这个特性。链表结构里天然包含了后继信息我们完全可以利用数学上的追赶问题来求解而不是简单地把所有节点都记下来。3. Floyd 判圈法快慢指针如何把环“跑”出来3.1 快慢指针的基本设定Floyd 判圈算法来自循环检测思想它在链表题的出场率极高。标准做法初始化两个指针 slow 和 fast都指向 head。slow 每次移动一步fast 每次移动两步两个指针同时移动。如果链表无环那么 fast 会在某一刻到达 null 或者 fast.next 为 null此时循环结束返回 null。如果链表有环那么 fast 和 slow 最终会在环内的某个位置相遇。需要注意相遇的位置一定在环内不可能在环外。因为 slow 一旦进入环它就在环内绕圈fast 已经比 slow 早进入环也一定在环内绕圈二者最终会追上。这里有个常见疑问为什么快指针每次走两步而不是三步、四步从原理上说只要两个指针速度不同它们在环内就存在速度差最终一定能够相遇。但选择“两倍速”有两个好处最小且直观的速度差慢指针走 1 步快指针走 2 步相对速度为 1 步/单位时间最容易分析追及关系数学推导简洁后续求入环点时两倍速的关系会产生极其干净的等式。用生活化的例子来说这就像操场跑步。慢者在前面跑快者在后面追只要跑道是闭合的快者一定会追上慢者。关键在于追上时快者已经比慢者多跑了一段“完整的环长”的整数倍。3.2 第一次相遇的代码框架我们先写一个只负责“判环”的版本方便理解def hasCycle(head): if not head or not head.next: return False slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False注意这里 while 条件写的是fast and fast.next因为 fast 一次跳两步只有确保 fast 和 fast.next 都不为空才能安全地访问 fast.next.next。在 142 题中我们不是立刻返回 True而是要在相遇之后继续操作找出入口。于是代码结构会变成def detectCycle(head): if not head or not head.next: return None slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: fast head while slow is not fast: slow slow.next fast fast.next return slow return None这段代码前半段是标准的判环后半段是关键把 fast 重新指向 head然后两个指针都以每次一步的速度前进。它们再次相遇的位置就是环的入口。4. 最关键的数学推导为什么“再次相遇点 入环点”4.1 参数定义与符号约定为了把推导讲清楚我们先定义几个符号。假设环的入口节点为 P头节点 head 到 P 的距离为 a。也就是说从头节点出发移动 a 步到达环的入口节点。假设第一次相遇点也就是 slow 和 fast 第一次碰面的节点为 M。从 P 节点出发顺时针移动 b 步到达 M。注意这里的顺序是头节点 → 入口 → 相遇点。从 M 继续顺时针移动 c 步会再次回到入口节点 P。那么环的长度 L b c。同时我们用 n 表示从速度较快的那根指针开始进入环到它与慢指针第一次相遇为止快指针在环内绕的完整圈数。n 是一个大于等于 1 的整数。用一张简单的示意图帮助理解head --a步-- P(入口) --b步-- M(相遇点) ^ | | c步 | ------------实际上环的结构可以看作三段a 是入环前的直线部分b 是入口到相遇点的那段弧c 是相遇点回到入口的那段弧。4.2 两倍速关系带来的关键等式现在开始推时间。当第一次相遇发生时我们假设 slow 走过的总距离是 S。slow 从头节点出发直到相遇这个过程中它最多只在环内走了一段弧 b不会重复绕圈。为什么因为在 slow 进入环之后快指针已经领先它一截慢指针可能还没走完一圈两指针就已经相遇了。严谨地说在第一次相遇发生前slow 在环内走过的长度必然不超过一圈。如果等于一圈它会回到入口 P而这时 fast 也在环内绕了整圈二者在入口处相遇等价于 b0 的情况也是允许的。所以 S a b。快指针走过的距离是 F。由于 fast 的速度是 slow 的 2 倍所以相同时间内 F 2 * S 2 * (a b)。另一方面快指针的路径可以从结构上分析它先走完 a 到达入口 P然后进入环内绕圈。在第一次相遇前fast 在环内绕了 n 圈整再多走一段弧 b最终到达相遇点 M。因此F a n * (b c) b这里的 (b c) 就是整圈环长 L。把两个 F 的表达式联立2 * (a b) a n * (b c) b化简2a 2b a b n * (b c) a b n * (b c)这个等式就是整个算法的核心。它的左边是 slow 走过的距离右边是 n 倍的环长。它告诉我们从头节点到相遇点的这段距离恰好是环长的整数倍。继续变形目标是解出 aa n * (b c) - b a n * (b c) - b a (n - 1) * (b c) c这个式子非常漂亮。它表明从头节点走到入口的步数 a等于“从相遇点 M 走 c 步回到入口 P然后再绕 (n-1) 整圈”的总步数。4.3 推导结果与第二次遍历的对应关系有了上面的式子接下来就顺理成章了。我们把 fast 指针重新放回 head然后两个指针都每次走一步。当 slow 从 M 点出发走 c 步它会先回到入口 P此时 fast 从 head 出发走 c 步它到了什么位置由于 a c (n-1) * L所以 fast 走了 c 步之后距离入口节点还差 (n-1) 圈。也就是说fast 还没到入口。但我们已经知道两个指针速度相同起点不同它们最终会在某个时刻相遇。现在从 c 步之后继续走fast 还需要走 a - c 步即 (n-1)*L 步才能到达入口而 slow 也在同时从入口 P 出发绕 (n-1) 圈最终也回到入口 P。所以二者再次相遇的位置正是入口 P。这段路程中两个指针恰好都走了 a 步构成一次精确会合。用更通俗的话总结第二次遍历时一个指针从 head 出发另一个从第一次相遇点出发它们速度相同。因为距离 head 到入口的步数与相遇点走回入口的步数加上若干个整圈相等所以当第一个指针走到入口时第二个指针也一定回到入口。于是两点相遇。注意这里的“走 c 步”是借用推导过程实际上代码里让两个指针同时一步一步走即可不需要人为控制步数。它们自行会相遇。4.4 一个具体数字例子为了让这个推导不那么抽象来一个实例。假设链表是 head(H) - 1 - 2 - 3 - 4 - 2其中节点 2 是环的入口 P。那么a 2H 到节点 1再到节点 2共 2 步环长为 4节点 2、3、4、2假设 slow 与 fast 第一次相遇发生在节点 4即 M 节点 4那么从入口 2 到 M 节点 4b 22 走一步到 3再走一步到 4从 M 回入口c 24 走一步到 2正好入口代入式子 a (n-1)*L c得 2 (n-1)*4 2可以取 n1满足条件。第一次相遇时fast 从 head 出发走 a b 2 2 4 步就到 Mslow 走 2 步也到 M而此时 fast 在环内只跑了 1 圈加 b 段二者正好相遇。第二次遍历时fast 回到 headslow 留在 M。两个指针同时走一步slow 到 2入口fast 到 H.next节点 1。第二次走一步slow 到 3fast 到 2。第三次走一步slow 到 4fast 到 3。第四次走一步slow 到 2入口fast 到 4。第五次走一步slow 到 3fast 到 2。第六次slow 到 4fast 到 3。第七次slow 到 2fast 到 4……这看起来没有相遇等一下我上面这段推演方向弄错了需要重新纠正避免误导。通常如果 n1那么 c 应该等于 a。上述 a2、c2 满足。第二次遍历时两个指针都每次一步从不同位置出发。fast 从 headslow 从 M。因为 a c 且 n1fast 走 2 步到入口 2slow 从 M 出发走 2 步也到入口 2。它们会在第 2 步同时到达入口正好相遇。所以下一次相遇就在节点 2 处。但刚才我上面从 M 点出发的第一个步长方向应该按原链表 next 方向走M4 的 next 指向 2所以 slow 第一步到 2第二步到 3第三步到 4……这就不对。这里出了问题关键在于我的例子符号方向我说“从 M 回入口c2”通常“相遇点 M”是通过 next 方向继续前进回到入口那么 M.next 就是指回入口。但我的示例里 4.next 是 2所以 M 的 next 确实回到入口 2。走一步就到 2c 应该等于 1 而不是 2。所以例子不匹配。为了让推导自洽我们应该让 bc 构成环长。假设环入口是节点 1这样重新举例H - 1 - 2 - 3 - 1其中 1 是入口。a 1环长 L 3。如果 slow 和 fast 第一次相遇在节点 3从入口 1 出发走一步到 2走两步到 3所以 b2从 3 走一步回到 1所以 c1。代公式 a c (n-1)L 1 0 1n1成立。第二次遍历中fast 从 head 出发slow 从 M节点 3出发各走一步fast 到 1slow 从 3 的 next 到 1。两人立刻在入口 1 相遇。完美匹配。所以一定要保证例子里 c 的步数与 next 方向一致。我重新设计例子时就别东扯西扯。用这个 H-1-2-3-1 例子就好head 记为 H节点 1 的值是1也是入口。这样例子简洁a1b2c1L3n1。第一次相遇点在节点 3第二次两个指针各走 1 步在入口 1 相遇。4.5 为什么快指针在第一次相遇前一定只比慢指针多跑 n 整圈这个点经常被追问。设相遇前 fast 在环内绕了 n 圈整这是根据速度关系自然得出的。因为 F 2SF - S S也就是相遇时快指针比慢指针多走的距离恰好等于慢指针的总距离。慢指针的总距离是 ab而 ab 恰好是环长整数倍已经推导过所以快指针比慢指针多跑的距离就是整数圈。这样一来n 的取值为正整数且通常比实际绕圈数更有解释意义。在一个环中只要速度差大于零快指针最终一定能赶上慢指针这就是循环追及问题的核心。5. 代码实现与边界条件处理5.1 Python 完整实现把上面的推导落实到代码最终版本非常简短class ListNode: def __init__(self, x): self.val x self.next None def detectCycle(head): if not head or not head.next: return None slow head fast head # 第一阶段找到第一次相遇点 while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: break else: return None # 第二阶段重新定位入口 fast head while slow is not fast: slow slow.next fast fast.next return slow这里有个 Python 技巧while...else结构。如果循环正常结束说明 fast 或者 fast.next 变成了空代表无环执行return None如果触发了 break说明找到了相遇点跳过 else 块。第二阶段不需要判空因为已经确认链表有环。两个指针一定会在进入环之前或进入环的瞬间相遇不会出现某个指针为空的情况。5.2 Java 与 C 版本参考用 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; } fast head; while (slow ! fast) { slow slow.next; fast fast.next; } return slow; } }C 同理注意判空和指针比较class Solution { public: ListNode *detectCycle(ListNode *head) { if (head nullptr || head-next nullptr) { return nullptr; } ListNode *slow head; ListNode *fast head; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { break; } } if (fast nullptr || fast-next nullptr) { return nullptr; } fast head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; } };5.3 边界情况单节点、双节点、无环链表的处理边界情况是这类题最容易写错的地方空链表 head null直接返回 null单节点无环节点 next 为 null返回 null单节点自环head.next head第一阶段 slow 和 fast 都会在第一步走到同一位置慢指针走一步到 head快指针走两步也到 head相遇点就是入口 head双节点环1 - 2 - 1入口是 1第一次相遇点也是 1长链无环第一阶段正常遍历fast 先到 null返回 null。在写代码时最好把对 head 和 head.next 的空检查放在最前面避免访问空指针的 next。6. 手写链路推演三种典型结构全步骤演示6.1 结构一无环链表链表 H - A - B - C - null。slow 和 fast 都从 H 出发轮次slow 位置fast 位置状态1HH初始2AB未相遇3Bnullfast 为空无环代码会执行return None。6.2 结构二环在链表尾部链表 H - A - B - C - D - B。入口是 B环长是 3B、C、D。我们按次序推进轮次slow 位置fast 位置1HH2AC3BB已绕一圈稍等需要计算这里不能简单罗列我们还是严谨一点初始都在 H第一轮 slow 到 Afast 到 C第二轮 slow 到 Bfast 到 B第二轮slow 从 A 到 Bfast 从 C 到 D 再到 B实际上 fast 一步跳两个节点C.next 是 DD.next 是 B所以 fast 第二轮到 B。slow 第二轮到 B二者正好在 B 相遇。此时 B 恰好就是入口返回 B非常顺利。如果换成链表 H - A - B - C - D - E - C入口 C环长 3初始在 H第一轮 slow 到 Afast 到 Cfast 从 H 两步跳到 C这不可能因为 head 到 A 是 1 步到 B 是 2 步到 C 是 3 步。fast 第一步从 H 跳到 B等等快指针一次跳两步从 H 出发第一步到达 BH→AA→B不是 C。慢指针第一步到 A。第二轮 slow 到 Bfast 从 B 跳两步到 DB→CC→D。第三轮 slow 到 Cfast 从 D 跳两步到 BD→EE→CD.nextEE.nextC所以到 C不对D 到 C 是两步也就是这一轮 fast 到达 C所以相遇点就是 C入口 C。用公式验证a2H→A→C注意 head 到入口 C 是 3 步从 H 出发到 A 需要 1 步到 B 需要 2 步到 C 需要 3 步所以 a3。但是 slow 走到相遇点 C 需要 3 步fast 速度是 slow 两倍走了 6 步。环长 L3fast 进环前需要走 a 步也就是从 H 到 C 走了 3 步然后入环绕 1 圈又到 C相遇。所以 n1。第二次遍历时 fast 回 headslow 留在 C两边一步fast 到 Aslow 到 DC→D没相遇第二步fast 到 Bslow 到 E第三步fast 到 Cslow 到 C相遇正是入口 C。完美。这两个例子说明相遇点不一定是入口但第二次遍历一定会相遇在入口。6.3 结构三环在链表头部附近链表 H - A - B - A。入口是 A环长是 2A、B。初始 H。第一轮slow 到 Afast 到 B。第二轮slow 到 Bfast 从 B 跳一步到 A不对fast 每次两步从 B 跳两步B.nextAA.nextB所以 fast 回到 Bslow 到 B二者在 B 相遇。相遇点 B入口 A。然后 fast 回 head两个指针同时走第一步 fast 到 Aslow 从 B 走到 A立刻相遇返回 A。这三个典型结构覆盖了无环、环在末端、环在头部附近三种场景代码逻辑一致。7. 常见错误与面试考点深度复盘7.1 最容易犯的三种错误错误一判空条件写漏。在 while 中用fast.next.next时如果 fast 本身是 null程序会抛出空指针异常。所以必须写成while fast and fast.next不能图省事。错误二初始指针设置不同。有些同学让 slow 先走一步、fast 先走两步再进入循环这时要额外考虑初始位置的相遇判断容易漏判。统一从 head 出发使用前插式判断代码更干净。错误三第一次相遇后直接返回相遇节点。这是这道题最常见的错误。相遇点不是入口直接返回的话如果数据恰好凑巧相同可能掩盖问题但绝大多数情况下会得到错误答案。必须重新移动 fast 到 head再走一次。7.2 面试官追问清单面试官在这道题上常见的追问包括如果不能修改链表结构你怎么做用上面的方法就是答案它不修改链表结构证明快慢指针一定会相遇吗追及问题速度差存在且轨道闭合如果快指针每次走三步还能用同样的相遇推论求入口吗原则上仍能相遇但不能推出 a c (n-1)L 这个简单等式因此常规解法固定用两倍速不要自行改动如何求环的长度第一次相遇后保持其中一个指针不动另一个指针每次走一步统计再次回到相遇点所需步数就是环长在这些追问里最需要重视的是数学推导要讲清。不要光说“这是模板”而是把 a b n(b c) 写出来一边写一边解释含义。面试官真正看重的不是背诵能力而是逻辑链是否完整。7.3 与链表其他题目的横向关联142 题的解法思想还能迁移到其他题目。141 题只判环不输出入口是 142 的简化版。876 题“链表的中间节点”快慢指针快指针每次两步、慢指针每次一步快指针到尾时慢指针恰在中点属于同一思想的另一个应用。160 题“相交链表”一种经典解法是把其中一个链表的尾部接到另一个链表的头部转化成环形链表求入口用的就是 142 的思想。所以这道题不是孤立的“背结论题”。一旦吃透了 Floyd 判圈法再去解决链表类的追及问题会顺手很多。8. 复杂度对比与无额外空间的现实意义8.1 两种方案的时间与空间对比方案时间复杂度空间复杂度特点哈希表法O(N)O(N)思路简单代码短但额外空间开销大Floyd 判圈法O(N)O(1)需要推导数学关系面试最优解这里的时间复杂度需要说明两个指针整体移动次数与链表长度成正比如果链表很长且环很小快指针可能需要在环内绕比较多圈才相遇但总体仍在 O(N) 量级。具体到本题的朴素理解就是从 head 到入环点加上环内有限次绕圈不会超过线性次数太多。Floyd 判圈法 O(1) 空间意味着它可以在不额外占用内存的情况下处理上亿节点的链表在真实场景中比如内存管理、网络数据包检测、文件系统循环引用检测等方向这种不增加存储开销的算法非常有价值。8.2 实际工程中的抽象意义链表环检测不只是面试题。在操作系统或数据库的日志记录、依赖关系解析、编译器符号表处理中可能会遇到对象引用形成循环引用的问题。能判断是否存在环、找到环的起点就可以进一步做循环清除或异常定位。比如某个垃圾回收器在扫描对象引用图时需要识别循环引用就可能采用类似的快慢指针思想。当然实际工程里情况更复杂但核心的“标记-检测-定位”逻辑与 142 题一脉相承。9. 这道题后续还能怎么扩展我自己每年刷到这道题都会重新推一遍公式不是因为记不住而是每次推都能加深对“追及问题”的理解。个人建议不要满足于把代码 AC。可以尝试自己编不同结构的链表比如入口在第一个节点、入口在中间、入口在最后一个节点、环长只有 1 等手动按指针路径模拟一遍。这样再遇到变体题比如“求环中包含的节点数量”或“判断两个链表是否相交”你会更快找到办法。扩展玩法是把链表结构换成数组形式的“跳跃游戏”给定一个数组每个元素表示下一步跳到哪个下标判断是否存在循环以及循环的入口。本质上就是 142 题的数组版但它的解法依然可以用快慢指针思想只不过下标访问代替了指针访问。能把链表题迁移到数组场景说明你对 Floyd 判圈的掌握才真正到位。如果后续想深入建议一并刷完 141、876、160 三道题形成一套“快慢指针四连”。这几道题放在一起既能通过对比理解不同场景下的细节差异也能为二叉树、图里的循环检测打下基础。最后分享一个我实际用起来很顺的小办法讲这道题的时候别急着写代码先在白板上画一条带环的链表然后用笔模拟快慢指针的每一步。画完之后公式推导自然就有了。真正理解之后你根本不需要背答案。