142. 环形链表 II

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function detectCycle(head: ListNode | null): ListNode | null {
    let a = head;
    let b = head;
    while(b && b.next){
        a = a!.next;
        b = b.next.next;
        if(a === b){
            let p = head;
            while(p !== a){
                p = p!.next;
                a = a!.next;
            }
            return a;
        }
    }
    return null
};

思路

使用快慢指针找到环的入口节点，分为两个阶段：

阶段一：检测是否有环

1. 初始化快慢指针 a 和 b 都指向 head
2. 慢指针每次移动一步，快指针每次移动两步
3. 如果有环，两指针必定相遇；如果无环，快指针会到达链表末尾

阶段二：找到环的入口

1. 当快慢指针相遇后，将一个指针 p 重新指向 head
2. 让 p 和慢指针 a 同时以相同速度（每次一步）移动
3. 当 p 和 a 相遇时，相遇点就是环的入口节点

数学原理

设链表头到环入口的距离为 $a$，环入口到相遇点的距离为 $b$，相遇点到环入口的距离为 $c$：

• 慢指针走过的距离：$a+b$
• 快指针走过的距离：$a+b+n(b+c)$（多走了 $n$ 圈）
• 因为快指针速度是慢指针的 2 倍：$2(a+b)=a+b+n(b+c)$
• 化简得：$a=(n-1)(b+c)+c$

这说明从头节点到环入口的距离 $a$，等于从相遇点再走 $c$ 的距离（加上若干圈）。因此让两个指针分别从头节点和相遇点出发，它们会在环入口相遇。

• 时间复杂度 $O(n)$，其中 $n$ 是链表的长度
• 空间复杂度 $O(1)$