数据结构与算法 / 系统课时

快慢指针与链表环

快慢指针与链表环

链表一旦形成环,普通遍历将无法到达 None。本课使用 Floyd 快慢指针算法,在常数额外空间内完成环检测与入口定位,并解释两阶段指针移动为什么成立。

学习目标

  • 掌握快慢指针检测链表环的标准循环条件
  • 理解第一次相遇后定位环入口的步骤
  • 正确处理空链表、无环链表和单节点自环

两阶段算法

第一阶段让 slow 每次走一步,fast 每次走两步。无环时,fast 或 fast.next 会到达 None;有环时,快指针进入环后每轮相对慢指针多走一步,最终必然在环内相遇。

第二阶段把一个指针放回 head,另一个保留在相遇点,两者都改为每次走一步,再次相遇的位置就是环入口。

Floyd 快慢指针检测与定位环入口

设头节点到入口距离为 aa,入口到相遇点距离为 bb,环长为 LL。相遇时慢指针走了 a+ba+b,快指针比它多走若干整圈,因此有:

2(a+b)=a+b+kL2(a+b)=a+b+kL

整理得 a=kL−ba=kL-b。从相遇点再走 aa 步,等价于沿环走到入口,所以两个同步指针会在入口相遇。

主示例

节点必须按身份比较,不能按值比较,因为不同节点可能保存相同数据。

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)。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

快慢指针与链表环

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通