算法 - 寻找环形链表入口节点 (Cycle Entry Node)

Posted on

1. 题目

给定一个链表的头节点 head，返回链表开始环路的节点。如果链表无环，则返回 null。

不允许修改链表。要求尽量用 O(1) 额外空间。

示例:

1
2
3
4
5
输入: head = [3,2,0,-4]，尾连回索引 1（值为 2 的节点）
输出: 索引为 1 的节点（环入口是值为 2 的节点）

输入: head = [1,2]，2 -> 1
输出: 值为 1 的节点

2. 解题思路

先判断有环（快慢指针），再定位入口。定位靠一个数学结论。

设：

  • head 到环入口距离为 a；
  • 环入口到「快慢相遇点」距离为 b；
  • 相遇点再走回环入口距离为 c（即环长 = b + c）。

相遇时：

  • slow 走了 a + b；
  • fast 走了 a + b + n(b + c)（在环里多绕了 n 圈）。

又因为 fast 速度是 slow 两倍：2(a + b) = a + b + n(b + c)，化简得：

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

含义：从 head 再走 a 步到达入口，等价于从相遇点走 c 步（再加若干整圈）也到达入口。

因此：相遇后，令一个指针 p1 回到 head，p2 留在相遇点，两者都每次走一步，再次相遇处即为环入口。

  • 时间复杂度：O(n)。
  • 空间复杂度：O(1)。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function detectCycle(head: ListNode | null): ListNode | null {
    let slow = head;
    let fast = head;

    // 阶段一：判断是否有环，找到相遇点
    while (fast !== null && fast.next !== null) {
        slow = slow!.next;
        fast = fast.next.next;
        if (slow === fast) {
            // 阶段二：一个指针回头，同速前进，再相遇即入口
            let p = head;
            while (p !== slow) {
                p = p!.next;
                slow = slow!.next;
            }
            return p;
        }
    }

    return null; // 无环
}

4. 面试延伸

  • 记住结论而非硬推：面试若时间紧，先说「用 Set 记录访问节点，第一个重复的就是入口」拿分，再补充 Floyd 法把空间降到 O(1)。
  • a = c + (n-1)·环长 是本题的灵魂，能手推这段等式是区分度所在。
  • 关联题：寻找重复数（LeetCode 287） 把「数组下标 -> 值」看成链表 next 指针，同样用 Floyd 找环入口，是本模板的巧妙复用。
  • 注意：相遇判断要放在两指针移动之后，否则初始都在 head 会误判。

难度：中等 | LeetCode 142 题 | Floyd 判圈算法