数据结构与算法 / 系统课时
用快慢指针处理链表环与中点
用快慢指针处理链表环与中点
快慢指针的核心不是“两个指针”本身,而是让它们以不同速度在同一条链上前进,再利用速度差制造可判断的相遇关系。掌握这个模型后,环检测、环入口定位和中点查找可以用一套思路完成。
学习目标
- 理解快慢指针为何能检测链表中的环
- 能由相遇点继续定位环入口
- 能根据奇偶长度选择需要的中点定义
先把速度差看成相对运动
设 slow 每次走 1 步,fast 每次走 2 步。若链表无环,fast 会先到达 None;若链表有环,两者进入环后都不会离开,而 fast 每轮相对 slow 多走 1 步,因此相对距离会不断缩小并最终相遇。
这和“快指针追慢指针”是同一个相对运动问题。关键判断不是记录访问过哪些节点,而是利用有限环内位置 + 固定速度差保证重复位置最终发生。

从相遇点定位环入口
第一次相遇只能证明有环,还不能直接把相遇点当作入口。Floyd 算法的第二阶段是:
- 保留一个指针在第一次相遇点。
- 另一个指针回到
head。 - 两个指针都改为每次走 1 步。
- 下一次相遇的位置就是环入口。
原因可以用距离关系理解。设从头节点到环入口距离为 ,入口到第一次相遇点沿环前进的距离为 ,环长为 。第一次相遇时,快指针走过的路程是慢指针的 2 倍,两者路程差又是若干个完整环,因此可以推出 与“从相遇点继续走到入口”的距离在模 意义下相等。于是从 head 和相遇点同时每次走 1 步,必会在入口碰面。
用同一模板查找中点
没有环时,快指针每轮走 2 步,慢指针每轮走 1 步。等 fast 到达末尾时,slow 恰好只走了大约一半距离,因此可直接得到中点。
常见模板 while fast and fast.next 有一个需要明确的边界:链表长度为奇数时返回唯一中点;长度为偶数时返回两个中间节点中的后一个。例如 1 -> 2 -> 3 -> 4 会返回节点 3。如果题目要求前一个中点,可以让 fast 初始从 head.next 出发。
完整实现并验证
下面同时实现环入口检测和中点查找。示例先构造一个 2 -> 3 -> 4 -> 5 -> 3... 的环,再构造无环链表验证中点。
class ListNode:
def __init__(self, val, next_node=None):
self.val = val
self.next = next_node
def detect_cycle(head):
slow = fast = head
# 第一阶段:利用速度差判断是否存在环。
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
return None
# 第二阶段:从 head 与相遇点同步前进,交点即环入口。
seeker = head
while seeker is not slow:
seeker = seeker.next
slow = slow.next
return seeker
def middle_node(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
if __name__ == "__main__":
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)
n2.next, n3.next, n4.next, n5.next = n3, n4, n5, n3
print("cycle entry:", detect_cycle(n2).val)
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
print("middle:", middle_node(head).val)预期输出
cycle entry: 3
middle: 3什么时候该想到快慢指针
看到链表题时,可以优先检查是否存在“位置随步数推进”的特征。题目问是否有环、环从哪里开始、中点在哪里,或者要求把链表按中点拆分,快慢指针通常都比哈希集合更节省空间。
但它不是万能模板。若题目要求找到倒数第 k 个节点,更自然的是固定间距的双指针;若要判断两个链表是否相交,则应利用长度差或尾节点关系。识别“速度差”“固定间距”还是“长度差”,比记住某一种双指针写法更重要。