05 快慢指针精讲：链表成环检测与 Floyd 判圈算法

快慢指针精讲：链表成环检测与 Floyd 判圈算法

摘要

快慢指针是链表问题中最优雅的算法工具之一。本文以 Linked List Cycle 为切入点，完整证明 Floyd 判圈算法的三个核心结论：快慢指针必然相遇、环起点的定位数学推导、环长的计算方法。然后将快慢指针推广到数组（Happy Number），展示同一算法框架在不同数据结构上的统一性。

---

第 1 章 为什么需要 Floyd 判圈算法

1.1 链表环检测的朴素想法

给定一个链表，判断它是否有环。最直觉的做法：遍历链表，把访问过的节点记录在 HashSet 中。每访问一个新节点，检查它是否已经在 HashSet 里——如果是，说明链表有环。

// 哈希表解法
public boolean hasCycle(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    ListNode cur = head;
    while (cur != null) {
        if (visited.contains(cur)) return true;
        visited.add(cur);
        cur = cur.next;
    }
    return false;
}

这个解法完全正确，时间复杂度 $O(n)$，但空间复杂度也是 $O(n)$（需要存储最多 $n$ 个节点的引用）。

面试题的常见追问：能用 $O(1)$ 空间解决吗？

这就是 Floyd 判圈算法（又称”龟兔赛跑算法”）的出发点。

1.2 Floyd 算法的直觉来源

想象一条操场跑道，有一段直线入口，然后是一个环形跑道。一只乌龟（慢指针）和一只兔子（快指针）同时从起点出发：乌龟每步走 1 格，兔子每步走 2 格。

• 无环：兔子会先到达终点，乌龟还在后面慢慢走——兔子先到 null。
• 有环：兔子进入环后开始绕圈，乌龟最终也进入环。此后，由于兔子速度更快，在环内相对于乌龟以速度 1 追赶，最终两者相遇。

这个直觉解释了”为什么快慢指针能检测环”，但面试中光靠直觉不够，需要能说清楚”为什么一定相遇”以及”相遇后如何找环的入口”。

---

第 2 章 LeetCode 141：链表是否有环

2.1 题目

LeetCode 141 - Linked List Cycle（简单）

给你一个链表的头节点 head，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true；否则，返回 false。

2.2 Floyd 算法解法

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;  // fast 到达末尾，无环
}

2.3 快指针判空顺序的细节

while (fast != null && fast.next != null) 中，必须先判 fast != null，再判 fast.next != null。

• 先判 fast != null：确保 fast 不是空指针，才能安全访问 fast.next
• 再判 fast.next != null：确保 fast.next 不是空指针，才能安全访问 fast.next.next

如果顺序反过来（先判 fast.next != null），当 fast == null 时访问 fast.next 直接抛出 NPE。

生产避坑：链表指针的判空顺序

任何链表操作，访问 node.next 之前必须先确认 node != null；访问 node.next.next 之前必须先确认 node != null && node.next != null。这是链表题最常见的 NPE 来源。

2.4 为什么快慢指针一定相遇（数学证明）

定理：若链表有环，快慢指针（快指针每步走 2，慢指针每步走 1）必然在有限步数内相遇。

证明：

设链表非环部分（从头节点到环入口）长度为 $F$，环长为 $C$。

第一阶段：慢指针进入环（步数 $\ge F$）。

当慢指针走了 $F$ 步到达环入口时，快指针已经走了 $2F$ 步，在环内的位置为 $2F\mathrm{mod}C$（从环入口算起，走了 $2F-F=F$ 步进入环后，在环内继续走 $F\mathrm{mod}C$ 步）。

不妨设此时快指针在环内位置为 $d=F\mathrm{mod}C$（从慢指针位置算，快指针领先 $d$ 步，也可以理解为快指针在慢指针”前面” $d$ 步，或者说慢指针在快指针”前面” $C-d$ 步）。

注意：这里”前面”指的是在环内相对于同一方向的距离。如果 $d=0$，两指针恰好在环入口相遇，无需追赶。

第二阶段：快指针在环内追赶慢指针。

每过一步，快指针比慢指针多走 1 步，即追赶距离减少 1。初始追赶距离为 $C-d$（慢指针在快指针”前面”的距离），经过 $C-d$ 步后，快指针追上慢指针，两者相遇。

总步数：$F+(C-d)$ 步（从慢指针进入环的那一刻算，这是一个有限数），因此必然相遇。$\square$

核心概念：相遇点不一定是环入口

快慢指针相遇的位置，一般不是环的入口节点，而是环内某个位置。找环入口需要额外步骤（见下一题 LeetCode 142）。

---

第 3 章 LeetCode 142：找环的入口节点

3.1 题目

LeetCode 142 - Linked List Cycle II（中等）

给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

3.2 数学推导：相遇点到环入口的距离

设快慢指针在环内某点相遇。此时：

• 慢指针共走了 $s$ 步
• 快指针共走了 $2s$ 步（速度是慢指针的 2 倍）

慢指针的路径：$F$ 步到达环入口，在环内走了 $s-F$ 步（在环内转了若干圈）。 快指针的路径：$F$ 步到达环入口，在环内走了 $2s-F$ 步。

由于在环内走任意圈数后回到同一位置（环长为 $C$），相遇条件：快指针在环内的位置 = 慢指针在环内的位置，即：

$2s-F\equiv s-F(\mathrm{mod}C)$ $s\equiv 0(\mathrm{mod}C)$

即 $s$ 是 $C$ 的倍数，设 $s=kC$（$k$ 为正整数）。

慢指针从头走了 $s=kC$ 步到达相遇点，其中 $F$ 步是非环部分，$s-F=kC-F$ 步是在环内走的。

关键推导：此时慢指针在环内的位置（从环入口算）是 $(kC-F)\mathrm{mod}C=(-F)\mathrm{mod}C=C-(F\mathrm{mod}C)$。

换个角度：从相遇点继续走 $F$ 步，在环内走了 $F$ 步，位置变为 $(C-F\mathrm{mod}C+F)\mathrm{mod}C=C\mathrm{mod}C=0$，恰好回到环入口！

结论：相遇点到环入口的距离 = $F$（链表头到环入口的距离）。

因此，找环入口的算法：相遇后，将一个指针重置到链表头，两个指针以相同速度（每步 1）移动，再次相遇的地方就是环入口。

3.3 完整解法

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    boolean hasCycle = false;
 
    // 阶段一：快慢指针找相遇点
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            hasCycle = true;
            break;
        }
    }
 
    if (!hasCycle) return null;  // 无环
 
    // 阶段二：将 fast 重置到头节点，两指针以速度 1 移动，再次相遇即环入口
    fast = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;  // 此时 slow == fast == 环入口节点
}

为什么阶段二将 fast 重置到 head，而不是 slow 重置到 head？

两者等价，重置哪个指针到头节点都正确（再次相遇的地方都是环入口）。习惯上重置 fast 到 head，因为 fast 在阶段一结束时在相遇点，slow 也在相遇点，任意重置一个到 head 即可。

3.4 特殊情况：相遇点恰好是环入口

当 $F\mathrm{mod}C=0$（即 $F$ 是 $C$ 的整数倍）时，慢指针进入环时，快指针也在环入口（绕了整数圈后回到入口），两指针立刻相遇。此时相遇点就是环入口，阶段二中 fast = head，slow 在环入口，两指针走 $F$ 步后均到达环入口，正确。

---

第 4 章 LeetCode 876：链表的中间节点

4.1 题目

LeetCode 876 - Middle of the Linked List（简单）

给你单链表的头节点 head，请你找出并返回链表的中间节点。如果有两个中间节点，则返回第二个中间节点。

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间节点，值为 3。

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：链表有两个中间节点，值分别为 3 和 4，返回第二个。

4.2 解法

public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

奇数长度（如 [1,2,3,4,5]）：fast 到达节点 5 时，fast.next == null，退出循环，slow 在节点 3（中点）。

偶数长度（如 [1,2,3,4,5,6]）：fast 到达节点 6 时，fast.next == null，退出循环，slow 在节点 4（第二个中点）。

找中点的快慢指针模板与环检测完全相同，区别只在于：找中点时不需要检查 slow == fast。

---

第 5 章 LeetCode 202：快乐数

5.1 题目

LeetCode 202 - Happy Number（简单）

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和
• 然后重复这个过程，直到这个数变为 1，也可能是无限循环但始终变不到 1
• 如果这个过程的结果为 1，则这个数是快乐数；如果最终进入无限循环，则不是快乐数

输入：n = 19
输出：true
解释：
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

5.2 为什么可以用快慢指针？

这道题表面上是数论题，与链表毫无关系。但仔细分析：“每次将数 n 替换为各位数字平方和”，这是一个函数：$f(n)=\text{各位数字的平方和}$。

如果不是快乐数，则 $n,f(n),f(f(n)),\dots$ 会进入一个无限循环，即这个数列构成了一个带环的序列（就像有环链表！）。

因此，判断 n 是否是快乐数，等价于：判断从 n 出发、不断应用 $f$ 的数列是否会到达 1（无环，最终停止），还是进入循环（有环，永远循环）。

这正是 Floyd 判圈算法的适用场景！

5.3 解法

public boolean isHappy(int n) {
    int slow = n;
    int fast = getNext(n);  // fast 比 slow 快一步
 
    while (fast != 1 && slow != fast) {
        slow = getNext(slow);           // 慢指针走一步
        fast = getNext(getNext(fast));  // 快指针走两步
    }
    return fast == 1;  // 如果 fast 到达 1，是快乐数；否则有环，不是
}
 
// 计算各位数字的平方和
private int getNext(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;
        sum += digit * digit;
        n /= 10;
    }
    return sum;
}

终止条件：

• fast == 1：快指针到达 1，是快乐数
• slow == fast：快慢指针相遇且不在 1，有环，不是快乐数

为什么不是快乐数的数列一定有环？

对于 3 位及以上的数 n（$n\ge 100$），$f(n)<n$（各位平方和必然比原数小，因为 $9^2\times \text{位数}<10^{\text{位数}-1}$，这个估算对所有实际输入成立）。所以 n 最终会被压缩到两位数范围内（$1\le n\le 99$）。

两位数的数列是有限的，只有 99 个可能的值，$f$ 必然会产生重复——即循环。因此不是快乐数的数一定会进入有限循环，Floyd 算法一定能在有限步内检测到。

---

第 6 章 快慢指针的共性与适用边界

6.1 快慢指针的共性模式

所有快慢指针问题都具备以下结构：

1. 存在一个”下一步”函数：链表中是 node.next，数组中可能是某个映射函数
2. 问题转化为环检测或距离计算：有环/无环、走到末尾的时间差
3. 节奏差产生信息：快指针走 2 步，慢指针走 1 步，节奏差最终带来两者相遇或差距恒定

6.2 快慢指针不适用的场景

• 双向链表：有 prev 指针，可以往回走，不需要快慢指针（可以直接找到中点）
• 数组（一般情况）：数组可以 $O(1)$ 随机访问，不需要快慢指针找中点（直接用 n/2 索引）
• 环检测问题但步幅不为 1 和 2：可能错过相遇点（如快 3 慢 1，在某些环长下可能不相遇）

生产避坑：快指针步幅选择

经典 Floyd 算法中快指针步幅为 2、慢指针步幅为 1。如果快指针步幅 $>2$，相遇不再有保证（例如步幅为 3 的快指针和步幅为 1 的慢指针，在长度为 2 的环中永远不相遇）。面试中除非特别说明，快慢指针的步幅固定为 2:1。

---

第 7 章 面试中的 Floyd 算法讲解方法

7.1 分阶段清晰表达

面试中讲解 Floyd 算法，推荐分三段：

第一段（环检测）：“快指针每步走 2，慢指针每步走 1。无环时快指针先到 null；有环时快指针在环内绕圈，慢指针进入环后两者以相对速度 1 追赶，最终相遇。”

第二段（相遇点性质）：“设非环部分长 $F$，环长 $C$，慢指针走了 $s=kC$ 步相遇，其中 $k$ 是正整数。从相遇点继续走 $F$ 步，恰好回到环入口。”

第三段（找入口算法）：“相遇后将一个指针重置到 head，两指针以速度 1 一起走，再次相遇的地方就是环入口，因为两者各走了 $F$ 步。“

7.2 常被追问的细节

“为什么慢指针走了 s = kC 步？”

慢指针从 head 走了 $s$ 步到达相遇点。相遇点是快指针追上慢指针的地方，快指针走了 $2s$ 步。两者路径的差 $2s-s=s$ 必须是环长 $C$ 的整数倍（因为它们在环内位置相同，只是绕了不同的圈数），所以 $s=kC$。

“为什么相遇点不一定是环入口？”

除非 $F\mathrm{mod}C=0$，否则相遇点在环入口沿环方向走了 $(kC-F)\mathrm{mod}C=C-(F\mathrm{mod}C)$ 步的位置，不是环入口。

---

小结

本文完整覆盖了快慢指针在环检测场景下的三个核心结论：

1. 有环时必然相遇：快指针以相对速度 1 追赶慢指针，$C-d$ 步后相遇
2. 相遇点到环入口距离 = 头节点到环入口距离：推导自 $s=kC$
3. 找环入口的实现：相遇后一个指针重置到头，同速移动，再次相遇即入口

同时将快慢指针推广到非链表场景（Happy Number），揭示了”序列中的函数映射形成隐式链表”这一通用思想。

下一篇继续链表双指针的实战题：删除倒数第 N 个节点、判断链表是否为回文、相交链表等，重点介绍”距离双指针”（先走 K 步，再同速移动）这一变体。