vvrf / DSA.log

问题拆解

不但要判断链表有没有环，还要返回环的入口节点。用哈希集合记录走过的节点，第一个重复出现的就是入口，O(n) 空间，一遍就完。进阶要求 O(1) 空间，这就得在 141 题快慢指针的基础上再榨出一点信息：相遇点的位置不是随机的，它和入口之间存在固定的数量关系。

设头到环入口的距离为 a，入口到相遇点为 b，相遇点绕回入口为 c（环长即 b + c）。相遇时慢指针走了 a + b，快指针走了 a + b + n(b + c)（多绕了 n 圈）。快指针路程是慢指针的两倍，所以：

2(a + b) = a + b + n(b + c)
a = (n - 1)(b + c) + c

a = (n-1)(b+c) + c 的含义是：从链表头走 a 步到入口，等于从相遇点先走 c 步到入口、再绕整 n - 1 圈。所以两个同速指针分别从头和相遇点出发，会在入口精确碰面。

Floyd 判环 + 二次同步走

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) { // 第一阶段：环内相遇
            ListNode p = head;
            while (p != slow) { // 第二阶段：同速走，必在入口碰面
                p = p.next;
                slow = slow.next;
            }
            return p;
        }
    }
    return null;
}

def detectCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:  # 第一阶段：环内相遇
            p = head
            while p is not slow:  # 第二阶段：同速走，必在入口碰面
                p = p.next
                slow = slow.next
            return p
    return None

func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if slow == fast { // 第一阶段：环内相遇
            p := head
            for p != slow { // 第二阶段：同速走，必在入口碰面
                p = p.Next
                slow = slow.Next
            }
            return p
        }
    }
    return nil
}

// LeetCode 的 Rust 链表用 Option<Box<ListNode>>，独占所有权无法成环，
// 官方也没有提供本题的 Rust 签名；这里用裸指针演示同样的两阶段逻辑。
pub unsafe fn detect_cycle(head: *const ListNode) -> *const ListNode {
    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 {
            // 第二阶段：一个从头、一个从相遇点，同速走
            let mut p = head;
            while p != slow {
                p = (*p).next;
                slow = (*slow).next;
            }
            return p;
        }
    }
    std::ptr::null()
}

推导里有两处容易含糊。一是 n ≥ 1：慢指针进环后一圈之内必被追上（相对速度为 1，差距最多环长），快指针至少已经完整绕过一圈，所以 n - 1 ≥ 0，第二阶段的指针不会“负着走”。二是当 a < c 时 n 会大于 1，从相遇点出发的指针要多绕几圈才到入口——等式对任意 n 都成立，代码里体现为两个指针各走各的，谁也不用知道 n 是多少。

实现上的细节：第二阶段两个指针都是一次一步，别惯性地让原来的快指针继续两步走；相遇判断放在两个指针都移动之后，否则起点 slow == fast == head 会被误判成相遇。

复杂度

指标	复杂度	原因
时间	`O(n)`	第一阶段最多 n + 环长步，第二阶段最多再走 n 步
空间	`O(1)`	只用三个指针

可以迁移的模式

快慢指针相遇后，“从头再派一个同速指针”是提取环入口的标准第二阶段；
路程关系 快 = 2 × 慢 是推导的唯一等式来源，类似题（如 287 寻找重复数）完全同构；
隐式链表（数组下标当 next）也能套 Floyd，判环不一定非得有真的链表节点。

把“相遇点携带的位置信息”翻译成等式再化简，是这类指针追逐题共同的解题动作。