环形链表 II 详解：从快慢指针到入环点的数学推导

我第一次做这道题不是在力扣提交页面，而是在一次模拟面试的白板上。当时我已经写出了 141 题的快慢指针解法，面试官点点头，然后追问了一句："如果链表有环，你怎么返回入环的那个节点？"我一下愣住了。用哈希表当然能解，但 142 这道题的名声就在于它要求 O(1) 空间。那一刻我才意识到，环形链表这个系列真正难过的地方，从来不是"判断有没有环"，而是"从有环推进到环在哪"。如果你也卡在这一步，这篇就当作一个踩坑复盘，我们一点一点把这道题啃透。

1. 题面拆解：环形链表 II 到底难在哪

1.1 题意与最朴素的解法

题目本身不长，一句话就能说完：给定一个链表的头节点head，返回链表开始入环的第一个节点；如果链表无环，则返回null。注意，题目还附带一个要求——不要修改链表结构。

最直白的解法是拿哈希表一路走一路记。每访问一个节点，先看它是否已经在集合里出现过，如果出现过，那么它就是环的入口；否则把它加进集合，继续往下走。

public ListNode detectCycle(ListNode head) { Set<ListNode> visited = new HashSet<>(); ListNode cur = head; while (cur != null) { if (visited.contains(cur)) { return cur; } visited.add(cur); cur = cur.next; } return null; }

这个思路直观到不能再直观，我自己第一次做这道题时就是这么 AC 的。代码提交通过，整个人挺高兴，但冷静下来发现一个尴尬的事实：这个解法的时间和空间复杂度都是 O(n)。在力扣的进阶要求面前，哈希表解法只能算半个答案。

1.2 为什么 141 到 142 的跳跃比想象中大

141 题问的是：链表中是否存在环。你只需要让快慢指针跑起来，如果某一刻两个指针指向同一个节点，就说明有环。141 的答案是布尔值，true 或者 false，代码写起来甚至比很多字符串题还短。

但 142 不一样，它要的不是"有没有环"，而是"环的入口节点在哪"。从判断存在到精确定位，难度上了一个台阶。很多人背过一个结论："相遇之后，把快指针挪回头节点，两个指针每次都走一步，第二次相遇的位置就是入口。"这句话流传很广，但如果你只是背下来，面试官一句"为什么两个指针第二次相遇一定在入口"，场面就会冷下来。

我自己也经历过这个"背得下来但解释不了"的阶段。后来在 IDE 里反复画图、推导，才真正搞明白这句话背后的数学关系。这也是我为什么坚持要写这篇的原因——网上的题解很多，但多数只给结论，不讲为什么。

1.3 面试中的真实考察点

这道题在面试中出现频率很高，因为它不是单纯背模板就能糊弄过去的。它把好几层能力揉在了一起：

• 基础数据结构：链表节点怎么遍历，怎么判断next是否为空；
• 算法范式：双指针思路，尤其是快慢指针的运用；
• 数学建模：把几何图形转化为变量和等式，这是最核心的一层；
• 表达与推导：能不能把相遇为什么要发生、入口为什么能定位讲清楚。

面试官真正在意的不是你"见过没有"，而是你"能不能现场推出来"。所以我强烈建议，哪怕你已经背下了代码，也要把第 3 节的推导完整走一遍。

2. 快慢指针检测环：龟兔赛跑背后的模数直觉

2.1 为什么慢指针不会被快指针"跳过"

很多初学者会有这个疑问：快指针每次走两步，慢指针每次走一步，快指针会不会直接越过慢指针，导致永远碰不到？

答案是不会。关键在于，快指针相对慢指针的速度是 1 步——快指针走两步，慢指针走一步，每个时间单位内，快指针比慢指针多走一步。如果它们都在环里，快指针每一次"相对靠近"的程度就是 1，不存在一次靠近 2 步的情况，自然也不可能越过对方。

你可以把环想象成一条圆形跑道，快指针和慢指针是两辆速度不同的车。因为相对速度只有 1，所以后车追上前车只是时间问题，不会有"嗖一下越过"这种戏剧性场面。

用钟表来类比更形象：分针走得比时针快，但它们的相对速度是固定的，所以在 12 小时内会相遇很多次，而不是分针一跳就跑到时针前面看不见了。

2.2 环内相遇的必然性与最坏情况

进一步追问：快指针为什么一定能在慢指针走完一圈前追上它？

这里有个严格的说法。假设慢指针刚到达环入口的那一刻，快指针已经在环内了，我们把快指针在环内"领先"慢指针的距离记为 d，且 0 <= d < L，其中 L 是环长。快指针每轮相对慢指针前进 1，那么最多 L-1 轮就能追上。也就是说，慢指针进入环后还没走出完整一圈，就会被快指针追上。

这个结论很重要，因为后面的推导要假设慢指针在相遇前没有走满一圈。如果慢指针真的绕了好几圈才被追上，那么慢指针的路程就不再是 a+b，而会变成 a + b + mL，公式会复杂很多。幸运的是，快指针的速度是慢指针的两倍，这个"两倍"保证了相遇发生得足够早，才让推导变得干净。

2.3 写检测部分代码时的第一个坑

判断环形链表的代码非常短，但初学者提交时最容易撞上的坑是空指针异常。很多人会写成这样：

while (fast.next != null && fast.next.next != null) { ... }

这个写法在head为null或者链表只有一个节点时会直接抛NullPointerException。因为fast本身可能已经为null，再去访问fast.next就崩了。

稳妥的循环条件应该是：

while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }

先保证fast非空，再保证fast.next非空，然后才能放心地执行fast.next.next。这个顺序看起来是小事，但我在调试里见过不少因为这个崩溃的代码，所以单独拎出来说一下。

3. 入环点的数学推导：相遇之后为什么还要再走一段

3.1 三个距离的设定

要理解入口定位，先定义三个关键距离。建议你手边拿张草稿纸，画一条带环的链表，边看边读：

• a：链表头head到环入口节点的距离（按边的数量计）；
• b：从环入口出发，沿着next方向走到快慢指针相遇点的距离；
• c：从相遇点继续沿next方向走，回到环入口的距离。

显然，整个环长L = b + c。这个分解是整个推导的基础。

画图的时候要注意，快慢指针的相遇点并不一定在环入口的正对面。它只是一个满足特定等式的几何位置，具体在哪取决于a和环长的关系。这也是为什么不能把相遇点直接当成入口。

3.2 等式变形与关键结论

忽略链表的入口和出口，我们只看路程。慢指针从head出发，到达相遇点时，总路程是a + b，因为它在环内还没走满一整圈就被追上了。

快指针从head出发，到达同一个相遇点时，总路程是a + b + kL，其中k是快指针在环内比慢指针多走的圈数，k >= 1。快指针速度快一倍，所以相同时间内它走的路程是慢指针的两倍：

2(a + b) = a + b + kL

两边同时减去a + b：

a + b = kL

进一步变形：

a = kL - b = (k - 1)L + (L - b)

由于L = b + c，所以：

a = (k - 1)L + c

这个等式是整道题的灵魂。它告诉我们：从链表头到环入口的距离a，等于从相遇点到环入口的距离c加上整数个环长。

于是我们可以设计一个非常优雅的操作：让一个指针从head出发，另一个指针保持在相遇点，两个指针都以步长 1 前进。当第一个指针走完a步到达环入口时，第二个指针走的路程是a步，也就是(k-1)圈再加c步，同样恰好绕回到环入口。两者在入口处相遇。

这就是"第二次相遇即入口"的真正来历。

3.3 直觉理解：用"取模"代替背公式

公式背起来容易忘，我后来给自己换了一种直觉理解，想通之后就再也丢不掉了。

快指针比慢指针多走的路程，恰好是环长的整数倍。多走的那段路程，数值上等于慢指针走过的路程，也就是a + b。这就意味着：慢指针从相遇点再走a步，会回到环入口。

与此同时，一个从head出发的指针走a步也会到达环入口。于是两个不同出发点、相同速度的指针，在走完a步之后，命运般地落在同一个点上。

我的记忆锚点是这样一句话：把相遇点当成一个临时起点，把head到入口的距离当成一段固定的旅程，那么相遇点到入口的距离在模环长的意义下，恰好等于这段旅程。一旦建立了这样的图景，代码里为什么要"重置一个指针到头节点"，就变得顺理成章了。

3.4 a=0 的边界情况：入口在头节点

很多人推导完公式就觉得大功告成，却忽略了一个特殊场景：环入口恰好就是头节点，也就是a = 0。

这种情况在题目里很常见，比如head指向自己形成自环，或者整个链表首尾相接，形成一个不算入口偏移的大环。此时公式变成：

0 = (k-1)L + c

当k = 1时，c = 0。这意味着相遇点就是这个环入口，两个指针第一次相遇的位置就在入口处。

代码里为什么会体现这个边界？因为当你重置一个指针为head后，如果head恰好就是入口，那么ptr == slow从一开始就成立，循环体不会执行，直接返回ptr。这是正确的行为，但如果你在写代码时没有意识到这一点，可能会怀疑自己的判断，甚至加一些多余的处理，导致出错。所以遇到这种用例时要淡定，程序是对的。

4. 直接可抄的代码与边界条件排查

4.1 Java 双指针完整实现

把上面的推导翻译成代码，就是下面这样。我用ptr作为从head出发的指针，避免复用fast造成混淆，可读性更好：

public class Solution { public ListNode detectCycle(ListNode head) { if (head == 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; } }

整段代码的骨架只有两个循环：第一个循环负责检测环并找到第一次相遇点，第二个循环负责从相遇点出发定位入口。很多人会把两个阶段混在一起写，结果越改越乱。分开写，思路清晰，也不容易出错。

4.2 边界条件一览表

我在调试这道题时整理过一份边界条件表，每次写完代码就照着过一遍，基本能筛掉大部分隐性 bug：

这张表我在手写代码前都会在脑子里过一遍。写代码时养成的习惯是：先把空指针、单节点、无环这三类最简单的场景跑通，再去看复杂环。

4.3 哈希表解法：O(n) 空间换直观

有时候面试官也会接受哈希表解法，尤其是当你先讲清楚思路，再补充一句"如果要 O(1) 空间，我会用快慢指针"之后。哈希表版本的代码前面已经给过了，它最大的优点是直观、不易出错、不需要任何数学推导。

它的缺点是空间复杂度为 O(n)。在极端情况下，比如链表有几十万个节点且环在很靠后的位置，哈希表会占用大量内存。力扣的进阶要求其实也在暗示：这道题最令人舒适的地方，不是朴素解法能 AC，而是你能不能用更优雅的方式解决问题。

另外多说一句，有人会想着"每访问一个节点就把它的 next 改成某个特殊节点"来打标记。这种思路可行，但它修改了链表结构，不符合题目要求，面试时也别这么回答。

5. 那些年踩过的坑：错解、陷阱与调试经验

5.1 网上流传的"错解"：把相遇点当入口

这道题在网上有一个流传度很广的误传：快慢指针相遇的位置就是环的入口。这个说法是错的，但因为它在一部分用例上"恰好能通过"，导致很多人被误导。

反例很容易构造。你画一个入口在位置 2、总节点数 4 的环形链表：1 -> 2 -> 3 -> 4 -> 2。快指针和慢指针第一次相遇大概率在节点 4 附近，离入口节点 2 还有一段距离。如果把相遇点直接返回，必然报错。

为什么这个错解还会流传？因为当a = 0且k = 1时，相遇点的确就是入口。有些刷题者只用了少量用例验证，就以为自己发现了"规律"，实际上只是巧合。这提醒我们，验证算法时一定要覆盖多种结构，不能只测 happy path。

5.2 空指针与死循环：while 条件怎么写才稳

我在第 2 节提过循环条件的坑，这里再展开说几个实操层面的细节。

第一个坑：fast.next.next。这个表达式要求fast和fast.next都不为 null。循环条件必须写while (fast != null && fast.next != null)，顺序还不能反。

第二个坑：在第二个循环里，如果误把ptr初始化为head.next，那么当入口就是head时，会陷入无限循环。因为ptr永远在slow前面追不上，或者两者交错。保险做法是ptr = head。

第三个坑：有环时，如果第二个循环的退出条件只写了while (ptr != slow)而忘记移动其中一个指针，就会死循环。两个指针必须同步移动。

我在本地调试时，习惯在循环内打印两行日志：

System.out.println("ptr = " + ptr.val); System.out.println("slow = " + slow.val);

这样每次都能直观看到两个指针的逼近过程。如果日志一直不出现相等的情况，那一定是循环逻辑写错了。

5.3 为什么快指针不能随便改成 3 倍速

这是一个超出主流题解范围的扩展问题，但面试官偶尔会问，而且真正理解的人不多。快指针如果改成每次走 3 步，检测环本身仍然是可行的，但有两个问题。

第一个问题是，相对速度变成了 2，快指针在环内可能"跳过"慢指针。假设某一时刻慢指针在前，两者距离为 1，快指针一次走 3 步，慢指针走 1 步，相对距离瞬间变成 -1，也就是快指针越过慢指针到了前面。因为快指针落点永远只在某个固定模数位置，两者的相遇就不再是必然事件。

第二个问题是，即使发生了相遇，入口的公式也不再是第 3 节推导出来的那个简洁形式。快指针速度改成 3 倍后，路程等式会变成3(a+b) = a+b+kL，推出来的关系式不再等同于"从 head 走 a 步等于从相遇点走 c 步加若干圈"。所以，2 倍速不是随便定的，它同时兼顾了"必然相遇"和"推导简洁"两个条件。

5.4 调试环形链表问题的实用技巧

调试这类问题，我有个固定的流程，分享出来供你参考。

第一步，先写一个辅助函数，用来快速构造带环链表。比如输入一个数组和一个入环位置下标，就能生成对应的环形链表。这样本地跑测试用例时不用手动拼接节点，省时省力。

public static ListNode buildCycle(int[] values, int pos) { if (values.length == 0) { return null; } ListNode dummy = new ListNode(0); ListNode cur = dummy; ListNode cycleEntry = null; for (int i = 0; i < values.length; i++) { cur.next = new ListNode(values[i]); cur = cur.next; if (i == pos) { cycleEntry = cur; } } if (cycleEntry != null) { cur.next = cycleEntry; } return dummy.next; }

第二步，先用哈希表解法跑一遍，确认"有环"这个前提成立。如果哈希表能返回入口，再跑双指针解法，这样可以把问题定位在"检测逻辑错"还是"入口定位错"。

第三步，用 4.2 的边界表逐条验证。尤其是自环和入口在头节点这两种情况，很容易出问题。

这套流程帮我省下了大量调试时间。你在刷题时也可以试试，特别是面对链表类题目，一个合适的辅助函数能省很多事。

6. 从力扣到实际工程：环形结构还能怎么用

6.1 287题：寻找重复数，一个让人拍案叫绝的转化

刷完 142 之后，这道题就变成了一道送分题。题目是这样的：一个包含n + 1个整数的数组nums，每个整数都在[1, n]范围内，所以至少存在一个重复的数。要求你找出这个重复的数，并且不能修改数组，只能用 O(1) 的额外空间。

这题最漂亮的解法，就是把数组想象成链表。索引i的下一个节点是nums[i]，也就是i -> nums[i]。因为所有nums[i]都在[1, n]范围内，所以从索引 0 出发，这条"链表"必然进入一个环，而环的入口就是那个重复的数。

public int findDuplicate(int[] nums) { int slow = 0; int fast = 0; // 第一阶段：在环内相遇 do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); // 第二阶段：找到环入口 int ptr = 0; while (ptr != slow) { ptr = nums[ptr]; slow = nums[slow]; } return ptr; }

我第一次看到这个转化时，心里是服气的。它把一个数组问题映射成链表问题，再套用 142 题的完整思路，全程不需要统计频率，不需要排序，不需要额外空间。这就是快慢指针方法论的高光时刻。

6.2 快慢指针的其他应用场景

快慢指针在链表题里是一整个家族，不止 142 这一道。我把它涉及的常见场景列一下，方便你举一反三：

• 141. 环形链表：只判断是否有环，快慢指针相遇即 true；
• 876. 链表的中间结点：慢指针走一步，快指针走两步，快指针到末尾时，慢指针正好在中点；
• 链表中倒数第 k 个节点：快指针先走 k 步，然后快慢指针同步走，快指针到末尾时，慢指针就是倒数第 k 个节点；
• 234. 回文链表：先用快慢指针找到中点，反转后半段，再逐一比较。

这些题的核心都是同一个思想：利用速度差制造相对位移，从而在单次遍历中完成某些查找或判断。掌握了 142 的推导，再去看这些题会轻松很多。

6.3 环形链表在真实系统里的身影

很多人刷题时会问：这东西除了面试，到底有没有用？环形链表的思想在真实系统里其实无处不在，只是不会直接写成ListNode而已。

操作系统里的时间片轮转调度，就是用一个循环队列（本质是环）让进程轮流使用 CPU。生产者消费者模型里的环形缓冲区，也是环状结构，用来在固定大小的内存区域里高效读写数据。垃圾回收算法在检测循环引用时，要判断对象引用图里是否存在环，思路和链表判环同源。文件系统里如果出现目录软链形成的循环引用，也需要类似的手段去发现和打破环。

这些场景里，"检测环"和"定位进入点"的思想会以各种形式反复出现。142 这道题的价值，不只是让你会写一个双指针函数，更是帮你建立一种识别环状结构的直觉。有了这种直觉，以后遇到类似问题，你会下意识地往快慢指针方向想。

最后分享一个我自己的土办法。学这道题时，我反复在本地用buildCycle构造各种奇形怪状的环，然后在关键位置打印日志，看slow和fast每一步落在哪个节点。跑了两三个用例之后，那个抽象的a、b、c关系就在脑子里扎了根。刷题这事，光看别人的推导永远差一层，自己动手画一遍、推一遍、在 IDE 里看一遍，才算是真正把它吞进去了。这题刷透之后，快慢指针这一整个分支基本就打通了，后面再去碰 141、876、287 都会顺畅得多。