环形链表 II

LeetCode 官方题目链接

1. 题目呈现

难度等级：🟡 中等
核心考察点：链表、双指针、数学

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

---

2. 解题思路拆解

方法：快慢指针 (Floyd 判圈算法 + 数学推导)

这道题在“判断是否有环”的基础上，需要找到环的入口。

1. 判断是否有环：

   • 和上一题一样，使用 fast (2步) 和 slow (1步) 指针。
   • 如果它们相遇，说明有环。

2. 找到环入口：

   • 假设链表头到环入口长度为 a。

   • 环入口到相遇点长度为 b。

   • 相遇点到环入口长度为 c (即环剩下部分的长度)。

   • 环的总长度为 b + c。

   • 相遇时：

     • slow 走的距离：a + b
     • fast 走的距离：a + n(b + c) + b (n 是 fast 在环里绕的圈数，n >= 1)

   • 因为 fast 速度是 slow 的 2 倍：

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

   • 结论：

     • 从表达式 a = (n - 1)(b + c) + c 可以看出：从链表头出发到环入口的距离 a，等于从相遇点出发，绕环 n-1 圈后，再走 c (相遇点到环入口) 的距离。
     • 简单来说，当 slow 和 fast 相遇后，我们让一个指针 ptr 从头开始走，另一个指针从相遇点继续走（此时速度都变为 1）。
     • 它们最终会在环入口相遇。

---

3. 代码实现

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let slow = head;
    let fast = head;
    
    // 1. 判断是否有环
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        
        // 相遇了，说明有环
        if (slow === fast) {
            // 2. 寻找环入口
            let ptr = head;
            // ptr 从头走，slow 从相遇点走，每次各走一步
            while (ptr !== slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            // 再次相遇点就是环入口
            return ptr;
        }
    }
    
    return null;
};

代码执行演示

输入 3 -> 2 -> 0 -> -4 -> (回到2) (a=1, 环长度=3)

1. 判环：
   • slow 和 fast 在 -4 处相遇。
   • 相遇点 -4。
2. 找入口：
   • ptr 从 3 开始。slow 从 -4 开始。
   • Step 1: ptr -> 2, slow -> 2 (回到环入口)。
   • ptr === slow，返回 2。

---

4. 复杂度分析

维度	描述
时间复杂度	$O(n)$。无论是判断环还是找入口，指针走的步数都是线性的。
空间复杂度	$O(1)$。只使用了几个指针变量。