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

用快慢指针处理链表环与中点

用快慢指针处理链表环与中点

快慢指针的核心不是“两个指针”本身,而是让它们以不同速度在同一条链上前进,再利用速度差制造可判断的相遇关系。掌握这个模型后,环检测、环入口定位和中点查找可以用一套思路完成。

学习目标

  • 理解快慢指针为何能检测链表中的环
  • 能由相遇点继续定位环入口
  • 能根据奇偶长度选择需要的中点定义

先把速度差看成相对运动

设 slow 每次走 1 步,fast 每次走 2 步。若链表无环,fast 会先到达 None;若链表有环,两者进入环后都不会离开,而 fast 每轮相对 slow 多走 1 步,因此相对距离会不断缩小并最终相遇。

这和“快指针追慢指针”是同一个相对运动问题。关键判断不是记录访问过哪些节点,而是利用有限环内位置 + 固定速度差保证重复位置最终发生。

快慢指针在链表环中的相遇与入口定位

从相遇点定位环入口

第一次相遇只能证明有环,还不能直接把相遇点当作入口。Floyd 算法的第二阶段是:

  1. 保留一个指针在第一次相遇点。
  2. 另一个指针回到 head。
  3. 两个指针都改为每次走 1 步。
  4. 下一次相遇的位置就是环入口。

原因可以用距离关系理解。设从头节点到环入口距离为 aa,入口到第一次相遇点沿环前进的距离为 bb,环长为 cc。第一次相遇时,快指针走过的路程是慢指针的 2 倍,两者路程差又是若干个完整环,因此可以推出 aa 与“从相遇点继续走到入口”的距离在模 cc 意义下相等。于是从 head 和相遇点同时每次走 1 步,必会在入口碰面。

用同一模板查找中点

没有环时,快指针每轮走 2 步,慢指针每轮走 1 步。等 fast 到达末尾时,slow 恰好只走了大约一半距离,因此可直接得到中点。

常见模板 while fast and fast.next 有一个需要明确的边界:链表长度为奇数时返回唯一中点;长度为偶数时返回两个中间节点中的后一个。例如 1 -> 2 -> 3 -> 4 会返回节点 3。如果题目要求前一个中点,可以让 fast 初始从 head.next 出发。

完整实现并验证

下面同时实现环入口检测和中点查找。示例先构造一个 2 -> 3 -> 4 -> 5 -> 3... 的环,再构造无环链表验证中点。

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

预期输出

text
cycle entry: 3
middle: 3

什么时候该想到快慢指针

看到链表题时,可以优先检查是否存在“位置随步数推进”的特征。题目问是否有环、环从哪里开始、中点在哪里,或者要求把链表按中点拆分,快慢指针通常都比哈希集合更节省空间。

但它不是万能模板。若题目要求找到倒数第 k 个节点,更自然的是固定间距的双指针;若要判断两个链表是否相交,则应利用长度差或尾节点关系。识别“速度差”“固定间距”还是“长度差”,比记住某一种双指针写法更重要。

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

目录与阅读设置

阅读设置

17

记录一个想法

用快慢指针处理链表环与中点

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

登录哪都通