数据结构与算法 / 系统课时
快慢指针与链表环
快慢指针与链表环
链表一旦形成环,普通遍历将无法到达 None。本课使用 Floyd 快慢指针算法,在常数额外空间内完成环检测与入口定位,并解释两阶段指针移动为什么成立。
学习目标
- 掌握快慢指针检测链表环的标准循环条件
- 理解第一次相遇后定位环入口的步骤
- 正确处理空链表、无环链表和单节点自环
两阶段算法
第一阶段让 slow 每次走一步,fast 每次走两步。无环时,fast 或 fast.next 会到达 None;有环时,快指针进入环后每轮相对慢指针多走一步,最终必然在环内相遇。
第二阶段把一个指针放回 head,另一个保留在相遇点,两者都改为每次走一步,再次相遇的位置就是环入口。

设头节点到入口距离为 ,入口到相遇点距离为 ,环长为 。相遇时慢指针走了 ,快指针比它多走若干整圈,因此有:
整理得 。从相遇点再走 步,等价于沿环走到入口,所以两个同步指针会在入口相遇。
主示例
节点必须按身份比较,不能按值比较,因为不同节点可能保存相同数据。
python
from dataclasses import dataclass
from typing import Optional
@dataclass(eq=False)
class ListNode:
value: int
next: Optional["ListNode"] = None
def find_cycle_entry(
head: Optional[ListNode],
) -> Optional[ListNode]:
slow = head
fast = head
# 第一阶段:检测快慢指针是否在环内相遇
while fast is not None and fast.next is not None:
assert slow is not None
slow = slow.next
fast = fast.next.next
if slow is fast:
# 第二阶段:一个指针回到头部,之后两者都每次走一步
reset = head
while reset is not slow:
assert reset is not None
assert slow is not None
reset = reset.next
slow = slow.next
return reset
return None
def main() -> None:
nodes = [ListNode(value) for value in [1, 2, 3, 4, 5]]
for index in range(len(nodes) - 1):
nodes[index].next = nodes[index + 1]
nodes[-1].next = nodes[2]
entry = find_cycle_entry(nodes[0])
print("有环入口:", entry.value if entry else None)
nodes[-1].next = None
entry = find_cycle_entry(nodes[0])
print("无环入口:", entry.value if entry else None)
if __name__ == "__main__":
main()运行命令:
bash
python linked_list_cycle.py预期输出:
text
有环入口: 3
无环入口: None边界与易错点
循环条件必须同时检查 fast 和 fast.next,否则执行 fast.next.next 时可能越界。第一次相遇点通常不是入口,不能直接返回;进入第二阶段后两个指针必须同速移动。
@dataclass(eq=False) 避免按字段递归比较节点。算法判断相遇应使用 slow is fast,因为值相同不代表两个引用指向同一节点。
两个阶段都只沿链表移动有限次,时间复杂度为 O(n)。算法只维护固定数量的节点引用,额外空间复杂度为 O(1)。
按自己的节奏,确认真正理解。