快慢指针：链表里的"龟兔赛跑"能解哪些题

链表没有随机访问，很多"需要全局信息"的问题（比如环、中点）似乎只能开额外数组存一遍。但快慢指针用两个速度不同的指针，就把空间压到了 O(1)。

用法一：判环（Floyd 判圈）。快指针每次 2 步、慢指针 1 步。无环时快指针先撞 null；有环时两者在环内相对速度差 1，必在有限步内相遇。相遇即证明有环，且还能进一步求出环入口。

用法二：找中点。快指针到尾时，慢指针恰好在中间——因为慢指针走的步数刚好是快指针的一半。这在不排序、O(n) 一遍找中点的场景（如归并排序链表版）极有用。

用法三：倒数第 k 个节点。快指针先走 k 步，然后两指针同步前进，快指针到尾时慢指针正好在倒数第 k 个。一趟遍历解决，无需先数长度。

快慢指针的精髓是"用时间换空间的对齐"——两指针速度差制造出"对齐点"，从而在单次遍历里拿到通常需要两次遍历的信息。它是链表题里性价比最高的技巧之一。

图：用速度差在单趟遍历里拿到中点/判环

参考代码（Python）

快慢指针用速度差在单趟遍历里拿到中点或判环。

def has_cycle(head):
    slow=fast=head
    while fast and fast.next:
        slow=slow.next
        fast=fast.next.next
    return slow==fast        # 相遇即有环

def find_mid(head):
    slow=fast=head
    while fast and fast.next:
        slow=slow.next; fast=fast.next.next
    return slow              # 快到尾，慢恰在中点

关联推荐

• 算法与问题求解入门 — "用对技巧，复杂度天差地别"的总入口
• 二分查找 — 同样是用"速度/区间"制造对齐来省空间
• 算法通关训练营·入门篇 — 链表与指针技巧的系统训练