适用读者：背过「快慢指针」模板，但被追问「为什么一定相遇」时只能答「就是会遇上」的人
技术栈：Python 为主，两种解法都附 Java 版
难度：简单（141）/ 中等（142）—— 但追问可以很深
收获：一个能当场写出来的相遇证明；一个被广泛传错的结论的纠正；以及「为什么偏偏是 2 和 1」的两条硬理由
题目
LC 141 环形链表：给你一个链表的头节点
head，判断链表中是否有环。
LC 142 环形链表 II：给定一个链表的头节点
head，返回链表开始入环的第一个节点。如果链表无环，则返回
null。
进阶（141）：你能用 O(1) 内存解决此问题吗？
输入：head = [3,2,0,-4], pos = 1
输出：true（141）/ 返回下标为 1 的节点（142）
解释：链表中有一个环，其尾部连接到第二个节点。
输入：head = [1,2], pos = -1
输出：false（141）/ null（142）
解释：链表中没有环。
约束：
- 链表中节点的数目范围是
[0, 10^4]
-10^5 <= Node.val <= 10^5pos 为 -1 或者链表中的一个有效索引- 142 要求不允许修改链表
节点定义沿用前三篇：
class ListNode:
def __init__(self, x=0, next=None):
self.val = x
self.next = next
留意两个细节。第一，
节点数可以到 10⁴——这个量级直接决定了哈希表法的空间开销值不值得。第二，
不允许修改链表——所以「把走过的节点标记一下」这类做法（改
val、改
next 指向哨兵）全部出局。这两句话把可行解的范围压得很窄，也把 Floyd 判圈推到了台前。
一、先把坐标系定下来
这题的证明之所以让人迷糊，多半是因为符号没统一。先把三个量钉死，后面所有推导都只用它们。
1.1 三个符号
设：
a —— 直段长度，也就是从头节点走到环入口的步数。注意「步数」和「下标」在这里恰好相等：head 的下标是 0，入口的下标就是 a。b —— 环的长度（环里有 b 个节点）。n —— 节点总数，n = a + b。
再加一个只在证明里出现的量：
x —— 相遇点沿环前进方向到入口的距离（0 ≤ x < b）。
本文的演示链表固定用
1 → 2 → … → 13，入口是节点 5，最后一个节点 13 指回 5。于是：
a = 4 （head 是 1，走到入口 5 要 4 步：1→2→3→4→5）
b = 9 （环是 5→6→7→8→9→10→11→12→13→5，9 个节点）
n = 13
后面动画和表格里的数字，全部来自这条链表。
1.2 最直接的做法：哈希表
「判断有没有环」最朴素的想法是：
一边走一边把走过的节点记下来，如果撞见一个记过的节点，那就是环。
def hasCycle(head):
seen = set()
while head:
if head in seen: # 又见到它了 → 有环
return True
seen.add(head)
head = head.next
return False
找入口更简单——
第一次重复出现的那个节点就是入口：
def detectCycle(head):
seen = set()
while head:
if head in seen:
return head # 第一次撞见的重复节点 = 环入口
seen.add(head)
head = head.next
return None
时间复杂度 O(n)，非常干净。但空间是
O(n)：最坏情况下（整条链表就是一个环，或者环很大）
seen 里要装下几乎全部 n 个节点。
n 最大 10⁴，看着不多。但「O(1) 内存」这道进阶题问的不是「10⁴ 个引用贵不贵」，而是
「能不能不靠额外存储就解决问题」——在流式数据、内存受限的嵌入式环境里，这是个真问题。而且面试官问出这句话的时候，期待的答案已经写好了：
Floyd 判圈算法（龟兔赛跑算法）。
二、Floyd 判圈：为什么一定相遇
2.1 代码
两个指针都从头出发，慢指针每步走 1 格，快指针每步走 2 格：
def hasCycle(head):
slow = fast = head
while fast and fast.next: # 快指针走得到头，就说明没环
slow = slow.next
fast = fast.next.next
if slow is fast: # 相遇 → 有环
return True
return False
Java 版：
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
代码五行。但「为什么这样一定能相遇」——这才是这题真正的考点。
2.2 把「相遇」翻译成一个同余式
先定义本文唯一要用的距离量：
gap = 快指针沿着前进方向，走到慢指针还需要几格。
（注意方向：是「快指针去追慢指针」，不是「慢指针去追快指针」。）
分两个阶段看。
阶段一：慢指针还没进环。 这时候快指针可能已经进环了，但
两者不可能相遇——慢指针在直段上，快指针在环里，位置集合根本不相交。所以相遇只可能发生在
慢指针进环之后。
阶段二：两个指针都在环上。 这时候每走一步：
- 慢指针沿环前进 1 格；
- 快指针沿环前进 2 格；
- 所以
gap 每步减少 fastStep - 1 格。
记
closing = fastStep - 1。对标准的「快 2 慢 1」，
closing = 1，
gap 每步减 1。
关键在于：环上的距离是
模 b 的。
gap 减到负数不会变成「负距离」，而是绕回环的另一端。所以
gap_k = (gap₀ - closing · k) mod b
相遇就是
gap_k = 0。这是一个同余方程：
closing · k ≡ gap₀ (mod b)
它有解，当且仅当
gcd(closing, b) 整除 gap₀（数论里的线性同余定理）。
所以问题归结成一句话：
gap₀ 长什么样？
2.3 关键一步：gap₀ 天生就满足整除条件
gap₀ 是「慢指针刚进环那一刻」的 gap。
慢指针走了
a 步到达入口（环上第 0 格）。同一时刻，快指针已经走了
a · fastStep 格，也就是比慢指针多走了
a · fastStep - a = a · (fastStep - 1) = a · closing
格。所以快指针在环上的位置是第
(a · closing) mod b 格，而慢指针在第 0 格。于是
gap₀ = (-a · closing) mod b
看这个式子。
a · closing 是
closing 的倍数；模
b 之后仍然是「
closing 的倍数再减去若干个
b」。而
gcd(closing, b) 同时整除
closing 和
b，所以它必然整除
a · closing 也整除
b，于是
它必然整除 gap₀。
整除条件自动成立。
方程一定有解，两指针必然相遇。
这不是「运气好」或者「试出来的」，而是代数上被锁死的。我把这件事直接枚举验证了一遍：
backend/venv/Scripts/python.exe tools/count_lc141_work.py
固定两指针同起点，对
fastStep ∈ {2,3,4,5}、
a ∈ [0,14]、
b ∈ [1,14] 全组合枚举，共
210 组每组：
四行都是 0。
2.4 一个被广泛传错的结论
写这篇文章之前，我原本准备照抄一个流传很广的说法：
（这个说法是错的，下面说为什么。） 「如果快指针走 3 步、慢指针走 1 步，那么当环长为偶数时，两个指针永远不会相遇。」
这个说法
在标准的同起点 Floyd 设定下是错的。上面那张表就是证据：快 3 慢 1 时，
closing = 2，枚举 210 组，
一次都没出现不相遇。
错在哪？错在
起点。
那个反例是真的，但它成立的前提是「两个指针从
不同位置出发」。如果两指针一开始就都在环上、快指针领先
d0 格，那么
d0 是
任意的，整除条件
gcd(closing, b) | d0 就不再被保证：
看
b = 6, closing = 2, d0 = 1 这一格：
gcd = 2 不整除 1，gap 序列在 1、5、3 之间打转，
永远碰不到 0。反例是真实的。
但标准 Floyd 是
两指针同起点，
gap₀ 被
gcd 锁死，压根走不到这个坑里。
把「不同起点」的结论套到「同起点」上，就是那个流传错误的来源。
顺带说一句：
b = 9 那一行全是「相遇」，因为
gcd(2, 9) = 1，此时无论
d0 是多少都能追上。这也是为什么这个错误说法特别容易「验证成功」——挑一个奇数环长去试，它看起来是对的。
2.5 看一眼动画
下面这个动画把演示链表
1→2→…→13（入口 5、
a = 4、
b = 9）的判环过程逐步演了一遍。
盯住环里那条
橙色弧线——它标的就是
gap，也就是「快指针沿前进方向到慢指针还差几格」。
每一步它恰好缩短 1 格，从 5 一路走到 0：
gap 序列：5 → 4 → 3 → 2 → 1 → 0
这条弧线就是「一定相遇」的全部直观内容：
gap 是模
b 递减的，而模
b 递减
不可能跳过 0。它必然依次经过
b-1、…、
1、
0。
第 9 步两指针在节点 10 相遇。核对一下账：慢指针走了 9 步，快指针走了 18 格，多走的
18 - 9 = 9 格正好是
一个环长。
2.6 相遇步数有闭式解
既然
gap 每步减
closing、模
b，那「慢指针进环后再走几步」就是解
closing · k ≡ -a · closing (mod b)。两边约掉
g = gcd(closing, b) 之后可得：
总相遇步数 t = 不小于 a 的最小 (b / gcd(closing, b)) 的倍数
拿演示链表验证：
a = 4、
b = 9、
closing = 1，
b / gcd(1, 9) = 9，不小于 4 的最小 9 的倍数是 9。
t = 9，和动画一致。
这个闭式解和暴力模拟在 840 组上逐项对照，
不符的有 0 组：
表里有个值得注意的地方：
快指针走得快，不代表更早相遇。
a = 7, b = 6 那一行，快 2 要 12 步，快 3 只要 9 步，而快 4 要 8 步——但快 5 又涨回 9 步。因为「多走的格数必须是环长的整数倍」这个约束会随
closing 一起变，步数不是单调的。
面试提醒：如果面试官只问 141，答到「
gap 每步减 1、必然经过 0」就足够了。但如果你能顺手写出
gap₀ = (-a · closing) mod b 这一步，说明你是真懂而不是背的。
三、LC 142：入口到底在哪
3.1 从相遇点能推出什么
设相遇点距入口
x 步（沿环前进方向，0 ≤ x < b）。
相遇那一刻，两个指针走过的距离是：
- 慢指针：
a + x（直段 a 步，再在环上走 x 步）
- 快指针：
2(a + x)（慢指针走的每一步，它都走两步）
而快指针比慢指针多走的部分，
必然是环长的整数倍（因为两个指针最终落在同一个节点上，多走的只能是绕圈）：
2(a + x) - (a + x) = a + x = m · b （m 是某个正整数）
把
a + x = m·b 改写成模
b 的形式：
这一步就是整道题的钥匙。 它的意思是：
从 head 走 a 步到入口；从相遇点走 b - x 步也到入口。两者相差的恰好是整数圈。
所以第二阶段的做法就顺理成章了：
- 把
ptr1 放回 head；
ptr2 留在相遇点；- 两个指针都改成每步走 1 格；
- 它们相遇的地方，就是入口。
因为
ptr1 走
a 步到入口，而
ptr2 走
a 步也到入口（
a ≡ b - x，差整数圈），
两条路一样长。
3.2 代码
def detectCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: # 第一阶段：找到相遇点
ptr1, ptr2 = head, slow # ptr1 回 head，ptr2 留在相遇点
while ptr1 is not ptr2: # 第二阶段：同速前进
ptr1 = ptr1.next
ptr2 = ptr2.next
return ptr1 # 相遇处即入口
return None
Java 版：
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode ptr1 = head, ptr2 = slow;
while (ptr1 != ptr2) {
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}
return ptr1;
}
}
return null;
}
整个算法
没有用任何额外存储，只有四个指针变量，与 n 无关。
3.3 看一眼动画
同一个链表
1→2→…→13，接着第一阶段的相遇点往下演。
左边那条
绿色标尺是
ptr1 从 head 到入口还差几步，环里那条
橙色弧线是
ptr2 从相遇点绕到入口还差几步。
两个读数是同步递减的：
ptr1：4 → 3 → 2 → 1 → 0
ptr2：4 → 3 → 2 → 1 → 0
演示链表特意选成
a = b - x = 4（
a = 4、
b = 9、
x = 5），所以两条路
一样长，两个读数严格同步。走满 4 步，两个指针同时落在节点 5——那就是入口。
这不是巧合，是刻意挑的：
a 和
b - x 只要求
同余，不要求相等。选成相等，动画上「两条路一样长」这件事才是肉眼可见的。
3.4 一个容易漏掉的边界：a = 0
如果
头节点本身就在环上，那么
a = 0，入口就是 head。此时相遇点也正好是入口（
x = 0），两个指针一开始就重合——
ptr1 一步都不用走。
代码上不用特判，
while ptr1 is not ptr2 一进来条件就不成立，直接返回
head。但
解释的时候要提一句，否则读者会以为「一定会有第二阶段的行走」。这也是我那个动画状态机里单独给
a === 0 留一帧
found 的原因。
另一个边界：
空链表（
n = 0）和
单节点自环（
b = 1）。前者两题都直接返回
false /
null；后者
b = 1 意味着环里只有一个节点，它自己指向自己——画图时不能用一条零长度的线表示，得画成一段弧，否则渲染出来什么都看不见。
四、为什么偏偏是 2 和 1
到这里，代码和证明都齐了。但面试官最爱追问的一句还没答：
为什么慢指针走 1、快指针走 2？走 3 行不行？
行。
但 2 和 1 是最优的，理由有两条，而且是两条独立的理由。
4.1 第一条：相对速度必须为正
closing = fastStep - 1。如果
fastStep = 1，那么
closing = 0——两个指针
每步走一样多，
gap 永远不变。它们会一直保持初始距离，永远不相遇。
所以
fastStep ≥ 2 是硬门槛。而
2 是满足这个条件的最小值——快指针每步跳过的节点最少，常数最优。
4.2 第二条：closing = 1 才让 LC 142 成立
这条更重要，也更容易被忽略。
回头看 3.1 节的推导。我们得到
a + x = m·b 这一步，用到了「快指针走的步数恰好是慢指针的两倍」。
如果快指针走 3 格，这个倍数就变成 3，于是：
3(a + x) - (a + x) = 2(a + x) = m · b
只能推出
closing · (a + x) ≡ 0 (mod b)，也就是
2(a + x) 是
b 的整数倍——
这推不出 a + x 是 b 的整数倍。当
b 是偶数时，
a + x 完全可以是
b/2 的奇数倍，此时
a ≡ b - x 就不成立了。
a ≡ b - x 不成立意味着什么？意味着
「ptr1 回 head、两者同速前进」这个解法直接失效——
ptr1 走到入口时，
ptr2 不在那儿。
我把这件事也枚举了一遍，统计「第二阶段能否成功」的比例：
只有快 2 慢 1 是 100.0%。 快 3 慢 1 有 55 组（26.2%）会让 LC 142 的解法失效，快 5 慢 1 更糟，31% 失效。
4.3 两条理由合起来
所以「2 和 1」不是随手选的惯例，而是
同时满足两条约束的唯一取值。
如果面试官只考 141，那第一条理由就够了（快 2 是相对速度为正的最小值，常数最优）。但如果两题连着考——
这才是美团那类「考环入口」的岗位真正想问的东西——第二条理由才是分水岭。
五、O(1) 空间那句话怎么答
进阶要求问的是「O(1) 内存」，所以最后把账算清楚。
5.1 空间账
- 哈希表法：
seen 里最多装 n 个节点引用 → O(n) 空间。
- Floyd 判圈：全程只有
slow / fast 两个指针变量（142 再加 ptr1 / ptr2）→ O(1) 空间，与 n 完全无关。
演示链表
n = 13 个节点，哈希表最坏要存 13 个引用，Floyd 永远是 2 个。
5.2 时间账
Floyd 并不比哈希表慢，仍然是 O(n)：
- 判环阶段：慢指针进环最多走
a 步；进环后 gap 每步减 1、模 b，最多 b - 1 步追上。总计 O(a + b) = O(n)。
- 找入口阶段：
ptr1 从 head 走 a 步，ptr2 走 a 步，也是 O(n)。
演示链表实测：判环阶段
9 步，找入口阶段
4 步，
两个阶段一共 35 次指针移动——而链表只有 13 个节点。多出来的是快指针的 18 格和第二阶段的两条 4 步。
5.3 汇总
结论：O(n) 时间和 O(1) 空间可以同时成立，代价是常数更大、且必须能改指针（所以「不允许修改链表」这条约束不影响 Floyd，它只动指针不动节点）。
六、面试速答
把上面的东西压成一段能在 90 秒内说完的话：
141 用 Floyd 判圈：慢指针每步 1 格、快指针每步 2 格，都从头出发。设慢指针进环那一刻快指针领先它 gap₀ 格，之后每步这个距离减 1——因为是模环长递减的，它必然经过 0，所以一定相遇。
为什么不是快 3？两条理由。一是相对速度必须为正，所以至少 2；二是 142 的「回 head 同速前进」要求 closing = 1，也就是快 2 慢 1，否则环长为偶数时推导会断。两条取交集，只有 2 和 1。
142 接着用相遇点：相遇时慢指针走了 a + x、快指针走了 2(a + x)，差值必然是环长整数倍，所以 a + x = m·b，即 a ≡ b - x (mod b)。于是把一个指针放回 head、两者同速前进，走 a 步后同时落在入口。
空间是 O(1)，只有几个指针变量，跟链表长度无关。
如果被追问「那快 3 慢 1 到底会不会相遇」——
会。只要两指针同起点，任何
fastStep ≥ 2 都必然相遇（
gap₀ 天生被
gcd 整除）。网上那个「环长为偶数时永不相遇」的说法，是把「两指针不同起点」的结论错套到标准 Floyd 上了。
七、本文的数字都是怎么来的
正文里的每个数字——相遇步数、gap 序列、枚举组数、成立占比——都由同一个脚本产出，可以自己跑：
backend/venv/Scripts/python.exe tools/count_lc141_work.py
：步数、距离、下标都是
确定性算术，同一份输入跑一百遍都是同一个数，不受机器负载影响。计时在这台机器上的噪声底是 12%，跨会话能涨到 57%，那种数字没有可复现性。
脚本里做了四件事：
- 用下标模型模拟标准 Floyd，暴力求出真实相遇步数；
- 对
fastStep ∈ {2,3,4,5} × a ∈ [0,14] × b ∈ [1,14] 全枚举，统计不相遇对数（四行都是 0）；
- 验证
gap₀ = (-a · closing) mod b 永远被 gcd(closing, b) 整除（840 组，0 例外）；
- 统计
closing ≥ 2 时 LC 142 第二阶段的失效比例（快 3 慢 1 已经漏掉 26.2%）。
第 3 条是「必然相遇」的代数证明的机器验证，第 4 条是「为什么必须是 2 和 1」的机器验证。两条都不是靠说服，是靠枚举。
三篇前作的对应关系：LC 206 讲的是「指针怎么反向」，LC 21 / LC 23 讲的是「哑结点 + 尾指针怎么接」，这一篇讲的是「两个指针的
速度差能推出什么」。链表题的三大套路——
反向、拼接、追及——到这里就齐了。