链表环检测 - Floyd 快慢指针算法完整指南

快慢指针技术（也称为 Floyd 龟兔赛跑算法）是计算机科学中最优雅的算法之一。它能在 O(1) 空间内解决链表环问题——在你理解背后的数学原理之前，这几乎像是魔法。

为什么面试官喜欢这个算法

1. 考察数学推理能力 - 证明它为什么有效能区分优秀的候选人
2. O(1) 空间约束 - HashSet 解法”太简单”；面试官想看 Floyd 算法
3. 多种变体 - 检测环、找环入口、找重复数字
4. 代码简洁 - 实现很简单，但洞察力很深

核心直觉：龟兔赛跑

想象一个环形跑道。乌龟（🐢）每次走 1 步，而兔子（🐇）每次走 2 步。如果跑道有环，较快的兔子最终会”套圈”较慢的乌龟，它们会相遇。

直线部分:    H ─── E ─── A ─── D
                              ↓
环形部分:                     ┌───────┐
                              │       │
                              C ←── Y │
                              │       │
                              └── L ──┘

关键洞察：如果存在环，快指针总能追上慢指针。它们必定在环内相遇。

---

交互式可视化

逐步演示算法。观察慢指针（🐢）和快指针（🐇）如何移动、在环内相遇，然后找到环的起始点：

Initializing...

---

第一部分：检测环（LeetCode 141）

题目：环形链表 (LC 141)

题目：给定 head，判断链表是否有环。

算法

1. 初始化两个指针：slow = head，fast = head
2. 每次迭代，slow 走 1 步，fast 走 2 步
3. 如果 fast 到达 null，则无环
4. 如果 slow === fast，则有环

代码模板

JavaPythonJavaScript

Loading...

为什么有效

定理：如果存在环，快指针最终会与慢指针相遇。

证明：

• 当两个指针都在环内时，考虑它们的相对位置
• 每一步，快指针和慢指针之间的距离减少 1（快走 2，慢走 1，净距离 = 1）
• 最终距离变为 0，它们相遇

第 0 步: slow 在位置 0, fast 在位置 0
第 1 步: slow 在位置 1, fast 在位置 2  → 距离 = 1
第 2 步: slow 在位置 2, fast 在位置 4  → 距离 = 2
...
进入环后: 每步距离减少 1，直到相遇

---

第二部分：找到环的入口（LeetCode 142）

题目：环形链表 II (LC 142)

题目：找到环开始的节点。如果没有环，返回 null。

这是算法真正精妙的地方。在找到相遇点后，我们可以用一个简单的技巧找到环的入口。

两阶段算法

第一阶段：找到相遇点（与环检测相同） 第二阶段：将一个指针重置到 head，两个指针都以 1 步的速度移动，直到相遇

代码模板

JavaPythonJavaScript

Loading...

---

数学证明：为什么第二阶段有效

这是让面试官印象深刻的部分。让我们证明为什么将一个指针重置到 head 并以相同速度移动能找到环的入口。

设定

数学推导

当 slow 和 fast 相遇时：

• 慢指针走过的距离：$F + a$（刚好到达相遇点）
• 快指针走过的距离：$F + a + nC$（在环中绕了 $n$ 圈，$n \geq 1$）

因为快指针的速度是慢指针的两倍： $2(F + a) = F + a + nC$

简化： $F + a = nC$

因此： $F = nC - a = (n-1)C + (C - a)$

这意味着什么

$F = (n-1)C + (C - a)$ 告诉我们：

• $(C - a)$ 是从相遇点到环入口的距离（沿环向前走）
• $(n-1)C$ 代表整圈的环

关键洞察：同时从 Head 和相遇点出发，每次走 1 步：

• 从 Head 出发：走 $F$ 步到达环入口
• 从相遇点出发：走 $(C - a) + (n-1)C = F$ 步到达环入口

它们恰好在环入口相遇！

可视化演示

---

第三部分：寻找重复数字（LeetCode 287）

题目：寻找重复数 (LC 287)

题目：给定一个包含 $n+1$ 个整数的数组，其中每个整数都在 $[1, n]$ 范围内，找出重复的数字。你必须使用 O(1) 额外空间。

洞察：将数组视为链表

将数组视为链表：

• 索引 $i$ 指向索引 $nums[i]$
• 重复的数字会创建一个环！

例子: nums = [1, 3, 4, 2, 2]

索引:   0 → 1 → 3 → 2 → 4
              ↓       ↓
值:     1   3   4   2   2
                      ↑
                 重复数字创建了环！

0 → nums[0] = 1
1 → nums[1] = 3
3 → nums[3] = 2
2 → nums[2] = 4
4 → nums[4] = 2  ← 回到索引 2！

环: 2 → 4 → 2 → 4 → ...
环入口 = 2（重复的数字！）

代码模板

JavaPythonJavaScript

Loading...

为什么有效

1. 因为值在 $[1, n]$ 范围内且我们从索引 0 开始，所以不会卡在索引 0
2. 重复的值意味着两个索引指向同一位置 → 形成环！
3. 环的入口点就是重复的数字

---

时间和空间复杂度

问题	时间	空间
检测环（LC 141）	O(n)	O(1)
找环入口（LC 142）	O(n)	O(1)
找重复数字（LC 287）	O(n)	O(1)

为什么是 O(n) 时间？

• 第一阶段：最多 2n 步（快指针最多遍历两遍）
• 第二阶段：最多 n 步（从 head 到环入口）

为什么是 O(1) 空间？

• 只用两个指针，与输入大小无关

---

🔥 为什么 fast 必须走 2 步？（重要证明）

这是一个高频面试追问。很多人以为 fast 走 3 步、4 步也可以，但实际上 只有走 2 步才能保证 100% 相遇！

核心洞察：相对速度决定一切

fast 步数	slow 步数	相对速度	距离变化
2	1	1	d → d-1 → d-2 → … → 1 → 0 ✓
3	1	2	d → d-2 → d-4 → … (可能跳过 0)
4	1	3	d → d-3 → d-6 → … (可能跳过 0)

关键：只有相对速度 = 1 时，距离每次减 1，必定经过 0（相遇）。

❌ 反例：fast 走 3 步永远追不上！

数学证明

设环长度为 $C$，fast 和 slow 之间的距离为 $d$。

相对速度 = 1（fast 走 2 步）： $d \to d-1 \to d-2 \to \cdots \to 1 \to 0 \checkmark$

每个整数都会经过，必定经过 0（相遇）。

相对速度 = 2（fast 走 3 步）： $d \to d-2 \to d-4 \to \cdots$

只经过偶数或只经过奇数。如果 $d$ 是奇数，会变成： $d \to d-2 \to \cdots \to 1 \to (1-2+C) = C-1 \to C-3 \to \cdots$

当 $C$ 是偶数时，距离在奇数之间循环，永远跳过 0！

通用规则

设 fast 每次走 $k$ 步，相对速度 $v = k - 1$。

相遇条件：$\gcd(v, C)$ 必须能整除初始距离 $d$

相对速度 $v$	$\gcd(v, C)$	能否保证相遇
$v = 1$	$\gcd(1, C) = 1$	总能整除任何 $d$ ✓
$v = 2$	$1$ 或 $2$	当 $C$ 偶数、$d$ 奇数时不能 ❌
$v = 3$	$1$ 或 $3$	可能不能 ❌

直观理解

相对速度 = 1（走 2 步）：
  ●───●───●───●───●───●───●───●
  d   d-1  d-2  d-3  ...  1    0 ✓
  每个整数都会经过，必定到达 0

相对速度 = 2（走 3 步）：
  ●───○───●───○───●───○───●───○
  d      d-2      d-4      ...
  只经过偶数或奇数，可能永远跳过 0！

相对速度 = 3（走 4 步）：
  ●───○───○───●───○───○───●───○
  d          d-3          d-6
  每 3 个数只经过 1 个，很可能跳过 0！

---

常见面试错误

错误 1：初始化错误

// ❌ 错误 - 会漏掉在 head 的环
let slow = head;
let fast = head.next;  // 不要这样做！

// ✅ 正确
let slow = head;
let fast = head;

错误 2：忘记空指针检查

// ❌ 错误 - 短链表会崩溃
while (fast.next) {
  fast = fast.next.next;  // 可能是 null！
}

// ✅ 正确
while (fast && fast.next) {
  fast = fast.next.next;
}

错误 3：第二阶段速度错误

// ❌ 错误 - 快指针仍然走 2 步
while (slow !== fast) {
  slow = slow.next;
  fast = fast.next.next;  // 应该是 1 步！
}

// ✅ 正确
while (slow !== fast) {
  slow = slow.next;
  fast = fast.next;  // 两个都走 1 步
}

---

边界情况

1. 空链表：head === null → 无环
2. 单节点无环：只有 head，head.next === null → 无环
3. 单节点有环：head.next === head → 有环，入口 = head
4. 环在头部：第一个节点就是环的入口
5. 长尾巴，小环：原理相同，只是需要更多步

---

相关题目

题目	难度	关键洞察
141. 环形链表	简单	基本检测
142. 环形链表 II	中等	找环入口
287. 寻找重复数	中等	数组视为链表
202. 快乐数	简单	数字序列中的环
876. 链表的中间结点	简单	快指针到终点时，慢指针在中间

---

面试技巧

如何向面试官解释

1. 从直觉开始：“想象一个有环的跑道…”
2. 解释第一阶段：“如果有环，快指针会追上慢指针”
3. 证明第二阶段：“从 head 到环入口的距离等于从相遇点到环入口的距离”
4. 写出简洁代码：从空指针检查开始，然后是两阶段算法

常见追问

问：你能用数学证明第二阶段吗？ 答：可以！使用等式 $2(F + a) = F + a + nC$，推导出 $F = nC - a$。

问：如果有多个重复数字怎么办？ 答：Floyd 算法找到一个环。对于多个重复数字，需要不同的方法。

问：如果快指针每次走 3 步可以吗？ 答：不行！ 走 3 步时相对速度 = 2，当环长度是偶数且初始距离是奇数时，fast 和 slow 永远不会相遇。详见上文”为什么 fast 必须走 2 步”的证明和反例。

---

总结

Floyd 环检测是面试必会的算法：

1. 检测环：快慢指针；如果相遇，则有环
2. 找环入口：相遇后，将一个指针重置到 head，都以 1 步移动
3. 数学原理：$F = nC - a$ 证明了第二阶段为什么有效
4. 应用：链表、找重复数字、快乐数

掌握这个算法，你就能自信地处理一整类面试问题！