快慢指针解决环形链表II：环入口的数学推导与实现

很多人在刷力扣142.环形链表 II这道题的时候，第一反应都是“我开个 Set 把走过的节点存下来不就行了？”，然后兴冲冲地写完一版能过的代码，觉得自己已经搞定了链表环的问题。但面试官往往会在你敲完哈希表解法之后追问一句：“能不能做到 O(1) 的空间复杂度？”这时候，快慢指针才真正登场。

这道题的核心其实有两层：第一层是判断链表里有没有环，第二层是如果有环，找出入环的第一个节点。只做第一层，哈希表确实够了；但要做到第二层且空间复杂度为常数，就需要把“相遇”这个现象背后的数学关系彻底想明白。这篇文章我会从最朴素的解法开始，一步一步把快慢指针的追及过程、环入口的数学推导、工程级代码实现以及相关变体题全部讲透。不管你是刚刷链表题的新手，还是准备面试想把这题讲出深度的人，都应该能从里面拿到点东西。

1. 先写一版能过OJ的哈希表解法

1.1 用Set记录节点：三行核心代码

先别急着上快慢指针，哈希表解法虽然空间复杂度不漂亮，但它能帮你快速确认“环入口节点”的定义，这是理解后续所有推导的地基。代码非常短：

def detectCycle(head): visited = set() cur = head while cur: if cur in visited: return cur visited.add(cur) cur = cur.next return None

逻辑是：每走到一个节点，先看它是否已经在 Set 里。如果在，说明这是第二次访问到它，这个节点就是环的入口节点；如果遍历到了空指针，说明链表没有环。这里有个细节容易忽略：为什么第一个“重复访问”的节点一定是入口，而不是环里其他节点？

因为链表是单向的，环入口是“从链表前缀进入环”的唯一通道。你从头节点出发，第一次进入环后，会依次经过环内所有节点，然后绕回来再次经过入口。在回到入口之前，环内其他节点的入度都是 1，只有入口节点会被第二次访问到。所以第一个重复出现的节点必然是入口，这个性质是后面所有解法都依赖的。

1.2 为什么哈希表解法只能算及格分

时间复杂度 O(n) 没毛病，但空间复杂度同样是 O(n)。如果链表特别长，或者面试官明确要求“能否只用常数额外空间”，哈希表解法就交不了差。

也许你会想：力扣提交能过不就行了？能过，但刷题不能只看 AC。这道题被归类为“中等难度”，真正的考核点不是“能不能想到哈希表”，而是“能不能想到用双指针把空间压到 O(1) ”，以及“能不能把数学原理讲清楚”。很多面试官甚至会在这个解法之后追加一句“如果节点数量上亿，Set 存不下怎么办”，这时候你不会快慢指针就会卡住。

所以哈希表方案适合作为“第一层思路”讲，但绝不能作为终点。

2. 快慢指针为什么一定能相遇：操场跑圈的追及模型

2.1 把环形链表理解成直道加跑道

快慢指针的代码框架很简单：快指针 fast 一次走两步，慢指针 slow 一次走一步。如果链表有环，两者一定会在环内相遇；如果无环，fast 会先走到空指针。这个结论很多人背过，但没想过原因。

我用一个生活化的类比：链表从 head 到环入口这一段是“直道”，进入环之后就是“操场跑道”。slow 和 fast 同时从起点出发，slow 速度是 1，fast 速度是 2。slow 到达入口时，fast 早就跑进跑道了，而且因为 fast 更快，它会在跑道里一圈一圈地跑。

关键点在于：当两者都在跑道内时，fast 相对 slow 的速度是 1。也就是说，每经过一轮迭代，fast 与 slow 之间的距离（按跑道上的弧长算）就会缩短 1 个节点。跑道长度是有限的，距离不可能无限缩小下去，所以两者必然会在某一轮结束后落在同一个节点上。这就是“相遇”的必然性。

2.2 fast走两步是设计出来的，不是拍脑袋

你可能会问：为什么 fast 是走两步，而不是走三步、四步？毕竟走三步理论也能追及啊。

这里有个很容易踩的坑：如果 fast 走三步、slow 走一步，两者的相对速度是 2，每轮相对距离缩短 2 个节点。但节点是离散的，如果环长和初始距离不匹配，fast 可能“跳过”slow 所在的节点，永远不落在同一个节点上。

举个例子：假设环长 L = 4，某一时刻 fast 领先 slow 1 个节点距离。fast 每轮相对逼近 2 个节点，距离变化是 1 → 3 → 1 → 3……永远到不了 0。也就是说，快三步在某些初始条件下根本不会相遇，程序会陷入死循环。

而 fast 走两步、slow 走一步时，相对速度为 1，每轮距离只会减少 1，任何整数距离都能在有限轮内归零，不存在“跳过”的问题。同时，速度差为 1 也让后面的数学推导变得非常干净。所以“两步”不是随手写的，是经过取舍后的最优设计。

2.3 一个容易被忽略的事实：fast可能已经绕了好几圈

还有一个细节很多人没意识到：当 slow 第一次进入环时，fast 已经在环内跑了一段距离；而 fast 追上 slow 之前，它可能已经在环内绕了不止一圈。

举个例子：链表 head 到入口距离很长，但环很小，比如只有 3 个节点。fast 先进入环，跑了好几圈之后 slow 才进来，此时 fast 离 slow 可能只差一点点距离，于是很快就追上了。这就意味着，相遇时 fast 比 slow 多走的路程不一定是“正好一圈”，而可能是好几圈。

这个观察很重要，因为后面推导环入口公式时，会有一个 n 表示 fast 比 slow 多绕的圈数。如果你默认 n = 1，在一部分用例下也能得出正确答案，但这个默认是错误的，会导致你无法理解公式的本质。记住：n 可以是任意正整数。

3. 相遇之后怎么找入口：一张轨迹表加一条等式

3.1 三个变量a、b、c的准确定义

先定义三个关键步数，后面所有推导都基于这些定义：

• a：从头节点出发，走 a 步到达环入口节点。例如链表 1→2→3，入口为 3，那么 a = 2。
• b：从入口节点出发，沿着 next 方向走到相遇点所需的步数。如果相遇点恰好是入口，则 b = 0。
• c：从相遇点出发，沿着 next 方向走回入口所需的步数。显然 b + c 正好等于环长 L。

这三个定义必须精确到“步数”，因为后面推导的是路程关系，不是节点个数关系。为了便于理解，我构造一个具体的链表例子：1 → 2 → 3 → 4 → 5 → 6 → 3，也就是说环入口是 3，环内节点是 3、4、5、6，环长 L = 4，a = 2。

下面这张表展示 slow 和 fast 每一步的位置：

相遇点是节点 5。从入口节点 3 出发，走 2 步到节点 5，所以 b = 2；从节点 5 出发，沿着 next 方向走回节点 3，路径是 5 → 6 → 3，共 2 步，所以 c = 2。环长 L = b + c = 4，完全吻合。

3.2 核心等式怎么推导

相遇时，两个指针经历的时间相同，fast 路程必然是 slow 路程的 2 倍。接下来我们分别算两者总路程：

• slow 从 head 到相遇点，经历了“从 head 到入口的 a 步”+“从入口到相遇点的 b 步”，总路程是 a + b。
• fast 从 head 到相遇点，经历了“从 head 到入口的 a 步”+“在环内绕的若干圈”+“从入口到相遇点的 b 步”。如果 fast 在相遇前比 slow 多绕了 n 圈，那么 fast 的总路程是 a + nL + b。

同时，fast 比 slow 多走的路程恰好是 n 圈整，也就是：

fast路程 - slow路程 = nL

再加上 fast路程 = 2 × slow路程，可以得到：

slow路程 + nL = 2 × slow路程
=> slow路程 = nL
=> a + b = nL

这个等式才是整个题目的核心。把它稍微变形：

a = nL - b = (n - 1)L + (L - b) = (n - 1)L + c

这个结论说的是：从 head 到入口的距离 a，等于“从相遇点走回入口的距离 c”再加上“若干个整圈”。也就是说，如果现在让一个指针 p 从 head 出发，另一个指针 q 从相遇点出发，两者都以速度 1 前进，那么 p 走到入口时，q 也已经绕了 (n - 1) 圈并走完 c 步，正好也在入口。两者必然在入口相遇。

这就是“相遇之后，把一个指针拉回 head，再同步走，第二次相遇处就是入口”的理论依据。

3.3 代入具体数值验证

回到上面那个例子。a = 2，b = 2，c = 2，L = 4，相遇时 fast 恰好比 slow 多走一圈，所以 n = 1。代入公式 a = (n-1)L + c = 0 + 2 = 2，完美吻合。

然后模拟算法：把 slow 重置到 head（节点 1），fast 留在相遇点（节点 5），两者每次走一步。

• 第 1 步：slow 到节点 2，fast 到节点 6。
• 第 2 步：slow 到节点 3，fast 到节点 3。

两者同时到达节点 3，这个节点就是环入口。如果 n 大于 1，比如 fast 多绕了两圈，那 fast 从相遇点出发会先绕一整圈回到相遇点，再走 c 步到入口。由于整圈不影响最终位置，算法依然正确。

所以这个算法的本质是：用“从相遇点绕回入口再绕若干圈”的路径，去凑出和 head 到入口一样长的距离。

4. 工程级实现：多语言代码与四个容易翻车的细节

4.1 Python版：比较对象比比较值更稳

Python 实现如下，注释里写了每一步的目的：

def detectCycle(head): slow = head fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: break # 无环的两种情况：fast 走到末尾，或 fast.next 走到末尾 if fast is None or fast.next is None: return None # 一个指针从头走，一个指针从相遇点走，速度都是 1 slow = head while slow is not fast: slow = slow.next fast = fast.next return slow

注意我全程用的是is而不是==。这是比较“节点对象本身”，而不是比较节点的值。链表里多个节点的 val 可能相等，但只有同一个对象才代表“同一个节点”。用==在某些重载了__eq__的节点类上也可能出现意外行为，而is永远是引用比较，最安全。

4.2 C++版：判空顺序决定你会不会崩

C++ 版本的逻辑和 Python 完全一致，但空指针判断的顺序非常关键：

ListNode *detectCycle(ListNode *head) { ListNode *slow = head; ListNode *fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) break; } if (!fast || !fast->next) return nullptr; slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; }

在 C++ 里，while (fast && fast->next)这个条件的顺序不能反过来。如果先判断fast->next，当 fast 已经是空指针时，直接解引用空指针崩溃。同理，循环体内先让 fast 走两步，也必须保证fast->next非空。

4.3 四个我在提交时才发现的坑

第一个坑是漏判单节点链表。如果链表只有一个节点，循环条件直接不成立，此时 fast 指向这个节点，fast->next 为空，判断fast->next是否为空返回 nullptr，这个路径没问题。但如果你在进入循环前没有判断 head 是否为空，而循环里又直接访问head->next，空链表会崩。所以最稳妥的做法是：不单独判空，完全依赖循环条件和 break 之后的if判断。

第二个坑是第一次循环结束后的“再次判断”。如果你在 while 循环里直接break，一定要在循环外面确认是因为相遇而 break，还是因为无环而退出。区分方法就是检查fast或fast.next是否为空。如果没有这一步就直接进入第二个 while，在无环链表中会出现一个指针已经为空的尴尬场面。

第三个坑是第二个 while 之前忘了重置 slow。很多人找到相遇点之后，直接让 fast 和 slow 继续走，想着“再相遇就是入口”。但如果不把 slow 拉回 head，两个指针都从相遇点出发、同速前进，它们会一直在环里同步转圈，永远找不到入口，程序死循环。

第四个坑是把无环判断写成了while fast and fast.next之后直接返回 slow。比如你写的是“相遇了就 break，没相遇最后返回 nullptr”，但因为 break 可能因为相遇触发也可能因为 fast 为空自动结束，你必须显式区分。我常用的做法是上面代码里的if fast is None or fast.next is None: return None，这一行看起来多余，但能规避一整类边界问题。

5. 从这题延伸出去：环长度、相邻题目与快慢指针的适用范围

5.1 相遇之后，怎么求环的长度

找入口会了，环长度就非常简单。既然两个指针已经在环内相遇，那让任意一个指针停在原地，另一个指针一次走一步，绕一圈回到这个位置时走过的步数就是环长。

也可以不额外开一个指针：相遇后让 slow 和 fast 都保持每次一步继续走，它们第二次相遇时，fast 恰好比 slow 多走一圈，而二者都走了一样的时间，所以第二次相遇时走过的总步数之差就是环长。不过最直观的做法还是“停一个，走一个”，代码更好写：

meet = fast # 相遇点 slow = fast fast = fast.next length = 1 while fast is not slow: fast = fast.next length += 1

这个length就是环长。

5.2 和142相邻的快慢指针题目长什么样

快慢指针在链表题里是一个非常体系化的套路，常见的有这么几道：

141 题只需要判断有没有环，不需要找入口，所以对比 142 少了第二段推导。876 题则更简单，快指针走完时慢指针正好停在中间。它们共同特点是：fast 走两步、slow 走一步，通过控制速度差来处理“位置关系”。

如果说 141 是快慢指针的入门，142 就是它最完整的形态——不仅要判断相遇，还要利用相遇点的几何关系反推出入口位置。把 142 吃透，再去做 141 和 876 会觉得轻车熟路。

5.3 快慢指针套路何时适用、何时别硬套

总结一下，快慢指针能用的场景有几个特征：存在单向的“移动关系”，可能是链表 next、数组索引；目标是找循环中的某个特殊点位，比如相遇点、入口、中点；对空间复杂度有 O(1) 要求。

但有一个场景千万别硬套：如果序列不是“单向函数式”的（也就是一个节点可能被多个节点指向），或者环的结构不是简单的单环，快慢指针的数学推导就不再成立。这时候老老实实用哈希表或者标记法反而更可靠。

另外，快慢指针不只是链表题的套路。检测随机序列是否出现周期、检测状态机的循环、甚至某些数据流中的重复模式检测，背后都是同样的思想：让两个“指针”以不同速度前进，相遇即说明存在循环。这也是为什么面试官喜欢从 142 题往深处问的原因——它考察的不是背题能力，而是对抽象模型的理解。

最后说点实在的。我刷这道题的时候一开始也是背结论：相遇后一个指针从头走，一个从相遇点走，再见就是入口。后来自己动手把 a、b、c 标在图上，把 n 从 1 改到 2 重新推演了一遍，才真正明白公式为什么成立。建议大家也别只看文章，一定自己拿一个具体的链表，比如本文里的 1→2→3→4→5→6→3，在纸上画两轮相遇过程。画完之后你会发现，这题并没有想象中那么“玄学”，快慢指针的每一个判断都来自清晰的几何关系，而不是凭空冒出来的。