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。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 轮 1 | slow=1,fast=2 | 都从节点 0 出发 |
| 轮 2 | slow=2,fast=4 | slow 刚入环 |
| 轮 3 | slow=3,fast=3 | 环内相遇 |
| 重新出发 | (0,3) → (1,4) → (2,2) | 两者同步到入口 |
窄屏可左右滑动表格,阅读完整计算与理由。
第一次相遇点未必是入口;第二阶段利用整圈差消除前导链长度。
04为什么这个方法成立
- 无环时快速指针必达尾部;有环时相对位置遍历环上的全部余数。
- 相遇后快慢路程差是环长整数倍。
- 重置后的同步行走在第 μ 步到达入口,之前前导链节点不在环内,不会提前相遇。
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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
一个节点指向自己,入口是谁?
需要一点提示
模拟第一轮。
查看解析与答案
两个指针都回到自身,入口就是该节点。
fast 改为三步还能直接沿用入口证明吗?
需要一点提示
相遇只说明 2t 是环长倍数。
查看解析与答案
不能直接沿用同一推导,t 未必为环长倍数;检测可能仍可设计,但入口阶段需重新证明。
找无环链表中点怎样用快慢指针?
需要一点提示
fast 到尾部时 slow 走一半。
查看解析与答案
slow 一步、fast 两步;偶数长度需先决定返回前中点还是后中点,再选择初始化和停止条件。