在链表操作中，快慢指针 (Fast & Slow Pointers) 是一种极其经典且优雅的技巧。它主要用于解决链表中的环路检测、中点寻找等问题。其背后的理论基础通常被称为 Floyd 判圈算法 (Floyd’s Cycle-Finding Algorithm)，有时也形象地被称为「龟兔赛跑算法」。

本文将从原理、可视化演示到数学证明，全面解析该算法在不同场景下的应用。

0x01 核心原理

算法的核心思想非常简单：初始化两个指针 slow 和 fast 指向链表头部。

  • slow：每次移动一步 ($step = 1$)
  • fast：每次移动两步 ($step = 2$)

如果链表中不存在环，fast 指针将率先到达链表尾部 (null)；如果链表中存在环，由于 fast 的速度快于 slow，它最终会在环内「追上」 slow 指针。

复杂度分析

  • 时间复杂度：$O(N)$。在没有环的情况下，遍历一次链表；在有环的情况下，两者入环后，fast 最多绕环一圈即可追上 slow。
  • 空间复杂度：$O(1)$。仅使用了两个指针，未使用额外的哈希表存储节点。

0x02 交互式算法演示

枯燥的文字不如直观的动画。下方的演示展示了一个带有环的链表（环入口为节点 3）。

  • 阶段一 (Phase 1)：点击「单步执行」，观察快慢指针如何移动并在环内相遇。
  • 阶段二 (Phase 2)：相遇后，算法如何利用「相遇点」和「新指针」找到环的精确入口。
慢指针 (x1) 快指针 (x2)
点击“单步执行”开始演示

0x03 典型应用场景

1. 判断链表是否有环

这是最基础的应用。只需判断 fast 和 slow 是否会重合。

代码逻辑

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}

2. 寻找环的入口节点

相遇只是第一步，更高级的应用是找到环的起始节点。这也是面试中的高频考点。

数学推导

假设链表头到环入口的距离为 $a$，环入口到相遇点的距离为 $b$，相遇点再回到环入口的距离为 $c$。也就是环的总长度 $L = b + c$。

  1. 当两者相遇时：

    • slow 走过的路程：$S_{slow} = a + b$
    • fast 走过的路程：$S_{fast} = a + n(b + c) + b = a + nL + b$ （$n$ 为 fast 在环内绕的圈数，通常 $n \ge 1$）

  2. 利用速度关系： 由于 fast 的速度是 slow 的 2 倍，所以 $S_{fast} = 2 \cdot S_{slow}$。 代入公式： $$ a + nL + b = 2(a + b) $$ $$ a + nL + b = 2a + 2b $$ 化简得： $$ a = (n - 1)L + c $$

  3. 核心结论： 当 $n=1$ 时（通常情况），公式简化为 $a = c$。 这意味着：从「链表头」到「环入口」的距离，等于从「相遇点」继续向前走到「环入口」的距离。

算法实现

基于上述推导，我们只需在通过阶段一找到相遇点后：

  1. 保持 slow 停在相遇点。
  2. 初始化一个新的指针（或直接复用 head）命名为 finder，放在链表头部。
  3. 让 slow 和 finder 同时移动，每次都只走一步。
  4. 它们再次相遇的节点，即为环的入口。

3. 寻找链表/环的长度

  • 环的长度：在找到相遇点后，可以让 slow 不动，用另一个指针绕环一圈回到 slow，统计步数即可。
  • 链表长度：如果存在环，链表长度通常定义为 $a + L$。

4. 寻找重复数 (数组应用)

有些数组问题可以转化为链表判圈问题。例如，数组中包含 $n+1$ 个整数，数值范围在 $[1, n]$ 之间，必定存在至少一个重复数。

我们可以将数组下标 i 视为节点，nums[i] 视为 next 指针指向的节点。由于存在重复数，意味着有多个下标指向同一个值（即多个节点指向同一个 next），这就形成了环。重复的那个数字，正是环的入口。

0x04 环的移除

在某些工程场景下（如内存回收、防止无限递归），我们不仅要检测环，还要从逻辑上打破环。 策略是：找到环的入口节点的前驱节点，将其 next 指向 null。

  1. 利用上述算法找到环入口。
  2. 由于我们已知入口节点，只需遍历环一圈，找到那个指向入口节点的节点（即尾节点）。
  3. 将尾节点的 next 置空。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// 伪代码示例
entry := detectCycleEntry(head)
if entry != nil {
    // 找到指向 entry 的那个节点
    curr := entry
    for curr.Next != entry {
        curr = curr.Next
    }
    // 断开环
    curr.Next = nil
}

0x05 总结

快慢指针是解决具有「循环」或「从末尾倒数」性质问题的利器。除了判圈，它也常用于：

  • 寻找链表的中点（归并排序链表时常用）。
  • 寻找链表倒数第 $k$ 个节点（等距双指针）。

掌握 $a=c$ 这一数学推导，是理解该工具上限的关键。