上一课我们玩了一把生命游戏，用一个二维数组让格子"活"了过来。这一课，我们把镜头拉回到第 2 课学过的链表，学一个面试里出现频率极高的技巧——快慢指针（fast & slow pointers）。

先记住：有些问题，用一个指针要跑两遍，用两个指针一快一慢，跑一遍就出答案。

一、什么是快慢指针

链表长得像一条单向的链子：

head → 1 → 2 → 3 → 4 → 5 → None

每个节点只有一条"出路"——指向下一个节点的指针 next。

快慢指针不是一种新数据结构，而是一种技巧：

  • 慢指针 slow：每次走 1 步（slow = slow.next）
  • 快指针 fast：每次走 2 步（fast = fast.next.next）

一个慢悠悠，一个两步并作一步。就是这个"速度差"，能帮我们解决一类经典问题：判断链表有没有环、找环的入口、找中点。

先定义链表节点：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val        # 存的值
        self.next = next      # 指向下一个节点

二、判断链表有没有环（龟兔赛跑）

想象一条链表如果有环，就像一条咬住自己尾巴的蛇，走啊走走不到头。怎么判断？让龟和兔一起从起点跑：

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:        # fast 能继续走两步
        slow = slow.next             # 慢走 1 步
        fast = fast.next.next        # 快走 2 步
        if slow is fast:             # 追上了 = 有环
            return True
    return False                     # fast 走到头(None) = 无环

直觉：如果没环，快指针会先走到 None，循环结束，返回 False。如果有环，快慢指针都在环里绕圈，快指针每绕一圈就比慢指针多追 1 步，迟早会"套圈"追上慢指针——这时返回 True。

注意两个细节：

  1. while fast and fast.next 这个条件很关键：因为 fast 每次走 2 步，必须保证 fast 和 fast.next 都存在，否则 fast.next.next 会报错。
  2. slow is fast 用 is 比较的是是否是同一个节点（身份相等），不是 val 相等。链表里两个不同的节点可能存着相同的值。

三、找到环的入口

光知道有环还不够，面试官常追问：环从哪个节点开始的？

这个问题的答案，藏在一个漂亮的数学事实里。先看代码，再讲为什么：

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                 # 无环，直接返回

    slow = head                     # 第二步：慢指针回到起点
    while slow is not fast:         # 两个都每次走 1 步
        slow = slow.next
        fast = fast.next
    return slow                     # 再次相遇处 = 环的入口

步骤拆开：

  1. 先让快慢指针相遇（和上一节一样）。
  2. 相遇后，把 slow 放回链表头 head，fast 留在原地。
  3. 两个指针都改成每次走 1 步，一起往前走。
  4. 它们再次相遇的那个节点，就是环的入口。

是不是有点反直觉？为什么「相遇点」和「起点」同时各走 1 步，会正好在环入口碰头？

四、为什么这样一定能找到环入口

把链表分成两段：

  • 环外的长度：a 个节点（从 head 到环入口，不含入口本身）
  • 环的长度：b 个节点（绕一圈）

设第一次相遇时，慢指针总共走了 s 步，快指针走了 2s 步（因为它快一倍）。

快指针比慢指针多走的步数是 2s - s = s。而它们相遇，意味着快指针在环里"套圈"追上了慢指针——多走的这 s 步，一定是环长 b 的整数倍：

s = n × b      （n 是某个正整数，套了多少圈）

再看慢指针。它从 head 出发走了 s 步，前 a 步在环外，剩下 s - a 步在环里。它现在停在环里的某个位置（相遇点）。

关键一步：从相遇点再往前走 a 步，会到哪里？

相遇点再走 a 步，总共在环里走了 (s - a) + a = s 步。而 s = n × b 是环长的整数倍——绕完整数圈，正好回到环入口！

所以结论成立：

  • 从起点走 a 步 → 到环入口。
  • 从相遇点走 a 步 → 也到环入口（绕整数圈回来）。

于是我们让一个指针从起点、另一个从相遇点，都每次走 1 步，各走 a 步后，它们必然在环入口相遇。这就是算法第二步的由来。

记住：相遇点到环入口的距离，等于起点到环入口的距离。

五、找链表的中点

快慢指针另一个高频用途：找链表的中间节点。

思路朴素得可爱：快指针每次 2 步、慢指针每次 1 步。当快指针走到头（None）时，慢指针正好走到正中间。

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

验证一下：

  • 长度 5（奇数）：1→2→3→4→5，快指针走到 5 后的 None 时，慢指针在 3，正好中间。
  • 长度 4（偶数）：1→2→3→4，快指针走到 4（fast.next 为 None 时停）时，慢指针在 3——这是中间偏右的那个（4 个节点，第 3 个）。
这个"中点"技巧，是后面学归并排序链表版、以及很多分治题的基石，先在这儿埋个伏笔。

六、找倒数第 k 个节点

这是快慢指针的一个"变体"——严格说是双指针，但套路相通：先让快指针领先 k 步，再两个一起走。

def find_kth_from_end(head, k):
    fast = slow = head
    for _ in range(k):            # 快指针先走 k 步
        if not fast:              # 链表不足 k 个节点
            return None
        fast = fast.next
    while fast:                   # 然后两个一起走
        slow = slow.next
        fast = fast.next
    return slow                   # 快指针到头时，慢指针就是倒数第 k 个

直觉：让快指针先拉开 k 个节点的距离。之后两个一起走，当快指针走到 None（末尾之外）时，慢指针离末尾正好还有 k 个节点——也就是倒数第 k 个。

记住：快指针先走 k 步，两个再齐步走，快到头慢就是倒数第 k。

七、复杂度分析：它快在哪

设链表有 n 个节点。

  • 时间：三个算法（判环、找中点、找倒数第 k）都只从头到尾走一遍，快慢指针加起来走的步数是 O(n)。找环入口要再走一遍，还是 O(n)。
  • 空间：全程只用 slow、fast 两个指针，O(1) 额外空间。

对比一下你就知道它的价值：找倒数第 k 个节点，如果不用双指针，你可能要先走一遍数总长度 n，再走一遍到第 n-k 个——也是 O(n) 时间，但要记一个长度变量；而快慢指针的写法更简洁。真正的威力在于判环：不用快慢指针，你很难在 O(n) 时间 + O(1) 空间里判断环的存在。

记住这个组合：O(n) 时间 + O(1) 空间，是快慢指针最值钱的标签。

八、小结

  1. 快慢指针 = 一个走 1 步、一个走 2 步，靠"速度差"一次遍历解决问题，不是新数据结构。
  2. 判环靠"套圈"：有环必然相遇，没环快指针先到头；找环入口靠"相遇点到入口的距离 = 起点到入口的距离"。
  3. 变体到处能用：找中点（快到头慢在中）、找倒数第 k（快先走 k 步再齐步走）——核心都是"拉开距离，再一起走"。

九、动手实验：三件事都验证一遍

把下面的代码整个跑一遍，看三个算法各打印什么：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build(values):
    head = p = ListNode(values[0])
    for v in values[1:]:
        p.next = ListNode(v)
        p = p.next
    return head

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

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
    slow = head
    while slow is not fast:
        slow = slow.next
        fast = fast.next
    return slow

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

def find_kth_from_end(head, k):
    fast = slow = head
    for _ in range(k):
        if not fast:
            return None
        fast = fast.next
    while fast:
        slow = slow.next
        fast = fast.next
    return slow

# 实验 1：判环 + 找入口
head = build([1, 2, 3, 4, 5, 6, 7, 8])
# 手动造一个环：让尾节点 8 指回 3（环外 1、2，环是 3→4→5→6→7→8→3）
node3 = head.next.next            # 值 3
tail = head
while tail.next:
    tail = tail.next
tail.next = node3                 # 造环
print("有环吗:", has_cycle(head))
entry = detect_cycle(head)
print("环入口的值:", entry.val)    # 期望 3

# 实验 2：找中点
head = build([1, 2, 3, 4, 5])
print("长度5中点:", find_middle(head).val)      # 期望 3
head = build([1, 2, 3, 4])
print("长度4中点:", find_middle(head).val)      # 期望 3（中间偏右）

# 实验 3：找倒数第 k 个
head = build([10, 20, 30, 40, 50])
print("倒数第2个:", find_kth_from_end(head, 2).val)   # 期望 40

跑完你会发现：三个问题，全都靠"两个指针一快一慢"就解决了——这就是快慢指针的优雅之处。

先别急着往后翻，把环亲手造出来再判断、再找入口，亲眼看到 entry.val == 3 打印出来，你对"套圈"和"相遇点→入口"的理解就彻底踏实了。

标签: none

添加新评论