vvrf / DSA.log

问题拆解

判断链表里有没有环。最直白的办法是用一个集合记录走过的节点，每到一个节点就查它是否出现过，重复出现就说明成环。这样能做，但要额外 O(n) 的空间。

进阶要求 O(1) 空间。既然不能记录走过的节点，就得换个思路：让两个速度不同的指针在链表上跑，用它们的相对位置来判断有没有环。

慢指针一次走一步，快指针一次走两步。如果没有环，快指针会先冲到 None；如果有环，两个指针迟早会在环里相遇。

快慢指针

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

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

func hasCycle(head *ListNode) bool {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast {
            return true
        }
    }
    return false
}

// LeetCode 的 Rust 链表用 Option<Box<ListNode>>，无法造环，
// 官方也没有提供本题的 Rust 签名；这里用裸指针演示同样的快慢逻辑。
pub unsafe fn has_cycle(head: *const ListNode) -> bool {
    let (mut slow, mut fast) = (head, head);
    while !fast.is_null() && !(*fast).next.is_null() {
        slow = (*slow).next;
        fast = (*(*fast).next).next;
        if slow == fast {
            return true;
        }
    }
    false
}

循环条件必须同时检查 fast 和 fast.next，因为快指针要连走两步，这两个位置都不能是空。一旦 fast 或 fast.next 为空，说明走到了链表尽头，无环。

为什么一定相遇

进入环之后，两个指针都在环里绕圈。把它们的距离看成“快指针要追上慢指针还差几步”，每一轮慢走一步、快走两步，这个差距就减少一格。差距是有限的整数，每轮减一，必然会减到零——也就是两指针落在同一个节点。它不会“跳过”慢指针，因为每轮只缩短一格，不可能一下从 1 跨到 -1。

复杂度

指标	复杂度	原因
时间	`O(n)`	慢指针进环后，最多再走一圈就被追上
空间	`O(1)`	只用两个指针，不额外记录节点

可以迁移的模式

判断链表有没有环、找环的入口、找中点，都可以用快慢指针；
关键在于设计两个指针的速度差，让它们的相对位置携带信息；
用 is 比较节点身份，而不是比较 val，因为值可能重复。

“两个指针不同速”是链表里非常通用的一招，值得当成模板记住。