专题进阶 · 数组技巧推荐总顺序 · 第 37 / 148 课

用相对速度解释环检测,再推导寻找环入口的第二阶段。

先学会这些,再进入本课 链表
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 数组技巧

快慢指针Fast & Slow Pointers

以不同速度遍历链表或状态转移,用于找环和中点。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

用相对速度解释环检测,再推导寻找环入口的第二阶段。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

单链表可能有环,不能靠遍历到 None 停止;怎样只用几个指针判断并找到入口?

02一步步得到方法

先讨论是否相遇

slow 每轮一步,fast 每轮两步。无环时 fast 最终遇到空指针;有环时两者最终都进入环。此后 fast 相对 slow 每轮多走一步,模环长看距离,会在至多一个环长内追上。

必须比较节点身份,不能比较节点值。不同节点可能都存 7;值相同不能证明回到了同一位置。

为什么重置一个指针就能找入口

设入环前长度 μ,环长 λ,slow 相遇时走了 t 步。fast 走了 2t,两者位置相同说明 t 是 λ 的倍数。相遇点相对入口的偏移等于 t−μ 对 λ 取模。

把一个指针放回 head,另一个留在相遇处,都每次一步。走 μ 步后,前者刚到入口,后者偏移 t−μ+μ=t,恰好绕整圈,因此也到入口;两者首次汇合就是入口。

把环看作模运算

设环长为 L,两指针进入环后每轮相对前进一格,距离差在模 L 意义下遍历,因此最终相遇。相遇只说明距离差为 L 的倍数,并不说明地点是入口。

设起点到入口距离 μ,入口到相遇点距离 x。由快慢路程关系可推出 μ+x 是 L 的倍数,所以把一个指针移回起点,两者各走一步,经过 μ 步会在入口重合。

03把一个小例子完全算清楚

0 → 1 → 2 → 3 → 4 → 2,入口为节点 2。

步骤计算与状态为什么这样做
轮 1slow=1,fast=2都从节点 0 出发
轮 2slow=2,fast=4slow 刚入环
轮 3slow=3,fast=3环内相遇
重新出发(0,3) → (1,4) → (2,2)两者同步到入口

窄屏可左右滑动表格,阅读完整计算与理由。

第一次相遇点未必是入口;第二阶段利用整圈差消除前导链长度。

04为什么这个方法成立

  1. 无环时快速指针必达尾部;有环时相对位置遍历环上的全部余数。
  2. 相遇后快慢路程差是环长整数倍。
  3. 重置后的同步行走在第 μ 步到达入口,之前前导链节点不在环内,不会提前相遇。

05把推导翻译成代码

Python · 可独立运行的教学实现

class Node:
    def __init__(self, value):
        self.value, self.next = value, None

def cycle_entry(head):
    slow = fast = head
    while fast is not None and fast.next is not None:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            first = head
            while first is not slow:
                first, slow = first.next, slow.next
            return first
    return None

逐个理解关键决定

fast.next is not None
每次跳两步之前先确认中间节点存在。
slow is fast
比较对象身份;不能用 value 相等代替。

06时间、空间与实现范围

最多走 O(μ+λ) 步,辅助空间 O(1)。用访问集合也能找环,但需 O(μ+λ) 空间。

该方法要求后继函数确定且遍历期间不变;并发修改链表会破坏推导。

07改变条件,检查哪里会出错

找到相遇节点直接称为入口

还需重置一个指针后的同步阶段。

未检查 fast.next 就走两步

空链表、单节点和无环链表都可能遇到空指针,应先检查再访问 next.next。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

一个节点指向自己,入口是谁?

需要一点提示

模拟第一轮。

查看解析与答案

两个指针都回到自身,入口就是该节点。

练习 2 · 边界与辨析

fast 改为三步还能直接沿用入口证明吗?

需要一点提示

相遇只说明 2t 是环长倍数。

查看解析与答案

不能直接沿用同一推导,t 未必为环长倍数;检测可能仍可设计,但入口阶段需重新证明。

练习 3 · 变式与迁移

找无环链表中点怎样用快慢指针?

需要一点提示

fast 到尾部时 slow 走一半。

查看解析与答案

slow 一步、fast 两步;偶数长度需先决定返回前中点还是后中点,再选择初始化和停止条件。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。