算法 - 5. 快慢指针

何时使用快慢指针

当你需要以不同速度探索链表来检测模式或查找特定位置时，使用快慢指针。虽然最常用于循环检测，但它也可以适用于：

循环检测（经典用例 - Floyd循环检测）
一次遍历找到链表的中间节点
查找链表中循环的起点
检测倒数第k个节点（通过保持间隔）
在链表中查找回文序列
任何通过以不同速率比较位置来揭示隐藏结构的问题

示例问题

有缺陷的生产线：想象一个工厂的圆形传送带，产品在上面排成一行移动。由于轨道缺陷，某些产品可能会循环回到早期点。

给定表示生产线上产品的链表：1 → 2 → 3 → 4 → 5 → 3（循环回来），确定：

生产线中有循环吗？
循环从哪里开始？

答案：是的，有一个循环，它从节点3开始。

最重要的洞察

以不同速度移动保证在循环中相遇 - 如果两个指针遍历链表，其中一个的移动速度是另一个的两倍，它们最终会在任何循环内相遇，而如果没有循环存在则会自然地在末尾停止。

思维笔记：算法的天才之处在于速度差异。快指针移动2步，而慢指针移动1步。在循环中，这创建了一个"追逐"，快指针以可预测的速度追上慢指针。如果没有循环，快指针只是首先到达末尾。这种简单的速度差异在不需要额外内存的情况下揭示了循环结构。

决策框架

在遍历的每一步，算法进行这些简单的检查：

快指针是否到达末尾？（null或next为null）→ 不存在循环
快指针和慢指针是否指向同一个节点？ → 检测到循环
继续以不同速度移动直到满足上述条件之一

代码

查找链表的中点

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number) {
    this.val = val;
    this.next = null;
  }
}

// 使用两个指针找到链表的中点。
// 时间：O(n)，空间：O(1)
function middleOfList(head: ListNode | null): ListNode | null {
  let slowPointer = head;
  let fastPointer = head;

  // 决策框架：继续直到快指针到达末尾
  while (
    fastPointer != null &&
    fastPointer.next != null &&
    // 在条件中包含slowPointer有助于TypeScript理解两者都不为null，
    // 注意逻辑上如果fastPointer不为null，那么slowPointer也不为null
    slowPointer != null
  ) {
    slowPointer = slowPointer.next;
    // 将快指针向前移动2步
    fastPointer = fastPointer.next.next;
  }

  // 当快指针到达末尾时，慢指针在中间
  return slowPointer;
}

// 使用示例：
// 链表：1 → 2 → 3 → 4 → 5
// 当快指针在5时，慢指针在3（中间）

检测是否存在循环

// 确定链表是否包含循环。
// 时间：O(n)，空间：O(1)
function hasCycle(head: ListNode | null): boolean {
  let slowPointer = head;
  let fastPointer = head;

  // 决策框架：继续直到指针相遇或快指针到达末尾
  while (
    fastPointer != null &&
    fastPointer.next != null &&
    // 在条件中包含slowPointer有助于TypeScript理解两者都不为null
    slowPointer != null
  ) {
    slowPointer = slowPointer.next;

    // 将快指针向前移动2步
    fastPointer = fastPointer.next.next;

    // 检查指针是否相遇（检测到循环）
    const pointersMetAtSameNode = slowPointer === fastPointer;
    if (pointersMetAtSameNode) {
      return true;
    }
  }

  // 快指针到达末尾 - 不存在循环
  return false;
}

// 使用示例：
// 带循环的链表：1 → 2 → 3 → 4 → 5 → 3（循环回来）
// 结果：true

查找循环的起点

// 确定链表是否包含循环并
// 返回循环的起点，否则返回null。
// 时间：O(n)，空间：O(1)
function cycleStart(head: ListNode | null): ListNode | null {
  let slowPointer = head;
  let fastPointer = head;

  // 阶段1：使用不同速度检测循环是否存在
  while (
    fastPointer != null &&
    fastPointer.next != null &&
    slowPointer != null
  ) {
    // TypeScript现在从循环条件知道slowPointer不为null
    slowPointer = slowPointer.next;

    // 将快指针向前移动2步
    fastPointer = fastPointer.next.next;

    // 检查指针是否在循环内相遇
    const pointersMetAtSameNode = slowPointer === fastPointer;
    if (pointersMetAtSameNode) {
      break; // 检测到循环，进入阶段2
    }
  }

  // 检查是否因为不存在循环而退出
  const fastPointerReachedEnd = fastPointer == null || fastPointer.next == null;
  if (fastPointerReachedEnd) {
    return null;
  }

  // 阶段2：找到循环的确切起点
  // 数学性质：从头部到循环起点的距离等于
  // 从相遇点到循环起点的距离（通过循环向前移动时）
  // -（详见下面的部分）
  //
  // 示例链表：1 → 2 → 3 → 4 → 5 → 6 → 3（循环从节点3开始）
  //   - 非循环部分：1 → 2（长度 = 2）
  //   - 循环部分：3 → 4 → 5 → 6 → 3（长度 = 4）
  //   - 相遇点：节点5（慢指针和快指针首次相遇时）
  //
  //   从头部（1）到循环起点（3）的距离：2步
  //   从相遇点（5）到循环起点（3）的距离：5→6→3 = 2步
  //   这些距离总是相等！

  // 决策框架：将一个指针重置到头部，两者以相同速度移动
  let pointerAtMeetingPoint = slowPointer;
  let pointerAtHead = head;

  while (
    pointerAtHead != null &&
    pointerAtMeetingPoint != null &&
    // 继续直到两个指针在循环起点相遇
    pointerAtMeetingPoint != pointerAtHead
  ) {
    // 一次移动两个指针一步（相同速度）
    const nextPositionFromHead = pointerAtHead.next;
    pointerAtHead = nextPositionFromHead;

    const nextPositionFromMeeting = pointerAtMeetingPoint.next;
    pointerAtMeetingPoint = nextPositionFromMeeting;
  }

  // 现在两个指针都指向循环起点
  return pointerAtHead;
}

// 使用示例：
// 链表：1 → 2 → 3 → 4 → 5 → 3（节点3是循环起点）
// 结果：值为3的节点

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

关键性质：当快慢指针在循环内相遇时，从头部到循环起点的距离等于从相遇点到循环起点的距离（通过循环向前移动）。

符号表示

让我们定义：

L = 非循环部分的长度（从头部到循环起点的距离）
C = 循环的长度
k = 从循环起点到相遇点的距离（沿循环测量）

阶段1（检测）中发生的事情

当指针相遇时：

慢指针行进了：L + k步（L进入循环，k更多到达相遇点）
快指针行进了：2(L + k)步（移动速度是两倍）

由于快指针在循环中，我们也可以将其位置描述为：

快指针行进了：L + k + nC步（其中n是完整循环的数量）

由于两者在同一位置：

2(L + k) = L + k + nC
2L + 2k = L + k + nC
L + k = nC
L = nC - k

关键洞察

从L = nC - k，我们可以重新排列来理解距离：

从相遇点到循环起点：

相遇点是进入循环k步的位置（从循环起点）。要返回循环起点，我们需要行进循环中的剩余距离：

循环中的剩余距离：向前C - k步
但我们证明了L = nC - k

代数分解nC - k：

为什么我们可以写nC - k = (完整循环) + (剩余距离)？

让我们使用除法来理解这一点：

当我们需要行进nC - k步时：
  nC - k = n × C - k
         = n × C - k - C + C，因为 - C + C = 0
         = (n-1) × C + C - k

这种分割为什么有意义：
  nC - k = (n-1)C + C - k
         = (n-1)C + (C - k)
           ↑         ↑
      完整      剩余距离
      循环      到循环起点

因此，nC - k = (完整循环) + (剩余距离)

这样想：
- 我们有n个完整循环（nC）
- 但我们减去k（循环中的位置）
- 这就像取(n-1)个完整循环，然后再取一个(C-k)的部分循环

视觉表示：
  如果你在循环中的位置k，需要行进nC - k步：
  - 首先做(n-1)个完整循环（回到位置k）
  - 然后再做(C - k)步（到达循环起点）

  这就是为什么nC - k总是等于(n-1)C + (C - k)

关键认识：在循环中，做nC - k步相当于做C - k步，因为(n-1)C部分只是绕循环(n-1)次并最终回到同一位置。

因此：

从头部L步 → 到达循环起点
从相遇点C - k步 → 到达循环起点
由于L = nC - k且nC - k ≡ C - k (mod C)，这些距离相等！

简单来说：从头部移动L步所需的实际步数与从相遇点移动C - k步相同，因为nC - k中的任何"额外循环"都不会改变圆形结构中的最终位置。

具体示例

链表：1 → 2 → 3 → 4 → 5 → 6 → 3（循环从节点3开始）

设置：
- L = 2（循环前的节点1、2）
- C = 4（循环：3 → 4 → 5 → 6 → 3）

阶段1 - 逐步追踪直到相遇

步骤0（开始）：
  慢：[1]      快：[1]

步骤1：
  慢：1 → [2]        快：1 → 2 → [3]

步骤2：
  慢：1 → 2 → [3]    快：1 → 2 → 3 → 4 → [5]
  （慢指针进入循环）

步骤3：
  慢：1 → 2 → 3 → [4]          快：1 → 2 → 3 → 4 → 5 → 6 → [3]
                                （快指针完成1个完整循环）

步骤4：
  慢：1 → 2 → 3 → 4 → [5]      快：1 → 2 → 3 → 4 → 5 → 6 → 3 → 4 → [5]

  ✓ 它们在节点5相遇！

为什么是节点5？

慢指针到达节点5需要4步
快指针到达节点5需要8步（移动速度是两倍）
一旦慢指针在步骤2进入循环，再需要2步（步骤3和4）才能相遇
快指针已经在循环中循环，每步缩小1个节点的差距

在节点5相遇后：
- 慢指针行进了：4步（L=2进入循环，k=2更多到节点5）
- 快指针行进了：8步（2到循环起点，然后6更多 = 1.5个循环）
- k = 2（从循环起点节点3到相遇点节点5的距离：3→4→5）
- 验证：L = nC - k → 2 = 1(4) - 2 ✓

阶段2 - 找到循环起点

两个指针以相同速度移动（每次1步）：

将一个指针重置到头部：
  pointerAtHead：[1]
  pointerAtMeetingPoint：[5]

步骤1：
  pointerAtHead：1 → [2]
  pointerAtMeetingPoint：5 → [6]

步骤2：
  pointerAtHead：1 → 2 → [3]
  pointerAtMeetingPoint：5 → 6 → [3]

  ✓ 两者都在节点3（循环起点）相遇！

两个指针正好行进了L = 2步，同时到达循环起点！

视觉证明

链表：1 → 2 → 3 → 4 → 5 → 6 → 3
      |___L___|_____循环____|
              ↑           ↑
          起点(3)    相遇(5)

从头部到起点的距离：L = 2
从相遇到起点的距离：(C - k) = (4 - 2) = 2

由于L = nC - k，我们在循环中向前移动C - k：
L ≡ C - k (mod C)

因此：从头部2步 = 从相遇点2步
两者同时到达循环起点！

这个数学性质使Floyd循环检测算法如此优雅 - 阶段2之所以能保证工作，是因为这个距离相等性。

疑虑消除

常见疑虑："为什么以不同速度移动能保证指针在循环中相遇？如果快指针一直跳过慢指针怎么办？"

这是关于Floyd循环检测算法的一个复杂问题。让我们用具体的推理来解决它。

为什么你可能认为快指针会错过慢指针

考虑链表中的一个循环。你可能会想：

"快指针一次移动2步，慢指针移动1步"
"在循环中，快指针难道不能直接跳过慢指针而永远不落在同一个节点上吗？"
"算法似乎假设它们会相遇，但这真的有保证吗？"

为什么这种想法是错误的

关键认识：在每次迭代中，快慢指针之间的差距恰好缩小1个节点！

让我们用相对速度的概念来理解这一点：

当两个指针都在循环中时：
- 快指针移动：每次迭代2个节点
- 慢指针移动：每次迭代1个节点
- 相对速度（快指针追赶慢指针）：2 - 1 = 每次迭代1个节点

这意味着它们之间的距离每次迭代恰好减少1个节点。

具体示例：差距总是缩小

让我们追踪一个有5个节点的循环，慢指针在位置0，快指针在位置3：

迭代0：
循环：[0] → [1] → [2] → [3] → [4] → [0]（循环）
        ↑           ↑
       慢          快
差距：前面3个节点

迭代1：
       [0] → [1] → [2] → [3] → [4] → [0]
              ↑                  ↑
            慢                  快
差距：前面2个节点（缩小1）

迭代2：
       [0] → [1] → [2] → [3] → [4] → [0]
                     ↑    ↑
                   慢    快
差距：前面1个节点（缩小1）

迭代3：
       [0] → [1] → [2] → [3] → [4] → [0]
                          ↑
                      慢和快相遇！
差距：0个节点（缩小1）

魔法：无论初始差距大小如何，每次迭代减少1意味着当差距达到0时它们必须相遇！

保证相遇的数学证明

在长度为C的循环中：

指针之间的初始差距：某个距离D（其中0 < D < C）
每次迭代差距减少：1个节点
直到相遇的迭代次数：D次迭代

为什么快指针不能"跳过"慢指针：

如果在迭代N时差距是2个节点：

N+1次迭代后，差距变为1个节点
N+2次迭代后，差距变为0个节点 → 相遇

不可能在一次迭代中从差距=2到差距=0，因为相对速度总是每次迭代1个节点。

为什么这在不同循环位置也有效

情况1：两个指针都从循环开始

每次迭代差距缩小1 → 保证相遇

情况2：指针在不同时间进入循环

一旦两者都在循环中，回到情况1
快指针先进入，然后等待慢指针
当慢指针进入时，每次迭代差距缩小1 → 保证相遇

Floyd算法的精妙之处

该算法利用了三个关键特性：

恒定的相对速度：总是每次迭代1个节点
圆形结构：差距环绕，无法逃脱
不可避免的收敛：D的差距需要恰好D次迭代缩小到0

这种组合保证了在任何循环内相遇，使算法既优雅又确定！

另一个常见疑虑

常见疑虑："如果循环极其巨大 - 像十亿个节点呢？指针在相遇之前不需要循环数十亿次，使这个算法实际上不可行吗？"

这是关于Floyd算法的合理性能问题。让我们看看为什么这种担心是没有根据的。

为什么你可能会担心大规模循环

考虑一个有循环的巨大链表。你可能会想：

"如果循环有10亿个节点，指针需要相互追逐绕循环"
"快指针可能会在最终相遇之前多次超越慢指针"
"这可能需要数十亿次迭代，使O(n)时间复杂度在实践中变得毫无意义"

为什么这种担心是不必要的

关键认识：指针在最多一次完整遍历循环内相遇，无论循环大小如何！

这是关键的洞察：一旦两个指针都进入循环，它们将在慢指针完成循环的一圈之前相遇。

具体示例：所需的最大迭代次数

让我们用最坏情况分析来证明这一点：

给定：
- 循环长度：C个节点
- 循环中慢指针位置：0
- 循环中快指针位置：1（仅领先一个节点 - 最坏情况）

迭代跟踪：
差距开始于：C - 1个节点（循环中可能的最大差距）
差距缩小：每次迭代1个节点
直到相遇的迭代次数：C - 1次迭代

结果：它们在少于C次迭代内相遇（少于一个完整循环）

带有"巨大"循环的真实示例

让我们追踪一个有10个节点的循环（代表十亿节点循环）：

最坏情况场景：
- 循环长度：10个节点
- 慢指针在位置0，快指针在位置1
- 最大差距：9个节点

迭代0：慢=0，快=1，差距=9
迭代1：慢=1，快=3，差距=8
迭代2：慢=2，快=5，差距=7
迭代3：慢=3，快=7，差距=6
迭代4：慢=4，快=9，差距=5
迭代5：慢=5，快=1，差距=4（快指针环绕）
迭代6：慢=6，快=3，差距=3
迭代7：慢=7，快=5，差距=2
迭代8：慢=8，快=7，差距=1
迭代9：慢=9，快=9，相遇！

总迭代次数：9（即C-1，其中C=10）

即使在绝对最坏的情况下，它们也只需要9次迭代就在10个节点的循环中相遇了！

时间复杂度保证

对于具有n个总节点的链表：

非循环部分：长度L个节点
循环部分：长度C个节点
总计：n = L + C个节点

阶段1（到达循环）：

慢指针需要L步进入循环
快指针最多需要L步
迭代次数：L

阶段2（在循环中相遇）：

慢指针进入时的最大差距：C - 1个节点
差距每次迭代缩小1
迭代次数：最多C - 1

总迭代次数：L + (C - 1) < L + C = n

这证明了算法是严格O(n) - 即使有十亿个节点的循环，你也最多遍历一次！

为什么这比使用哈希集更好

与跟踪访问过的节点的朴素方法相比：

哈希集方法：
- 时间：O(n)
- 空间：O(n) - 存储每个访问过的节点

快慢指针：
- 时间：O(n)
- 空间：O(1) - 只有两个指针

对于10亿个节点：
- 哈希集需要约8-16GB的内存
- 快慢指针需要约16字节（两个指针）

数学之美

最坏情况场景实际上受到一个美丽特性的限制：

最大迭代次数 = n - 1

其中n是总节点数。这意味着：

100个节点 → 最多99次迭代
1,000个节点 → 最多999次迭代
1,000,000,000个节点 → 最多999,999,999次迭代

你永远不会"无休止地循环" - 该算法有一个硬性上限，与输入大小成线性比例，即使对于大规模循环也极其高效！