环形链表 II

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

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

不允许修改链表。

示例 1：

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

输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。示例 3：

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

进阶做法：要找到链表入环的第一个节点（若有环），可以在快慢指针判断有环的基础上，通过二次相遇定位入环点，时间复杂度O(n)，空间复杂度O(1)，且不修改链表。

核心思路

判断是否有环：用快慢指针（慢指针走1步，快指针走2步），若相遇则有环，否则无环。
定位入环点：
- 当快慢指针相遇后，将慢指针移到链表头部，快指针留在相遇点。
- 两指针以相同速度（每次1步）移动，再次相遇的节点即为入环的第一个节点。

原理证明

设：

头节点到入环点的距离为 a；
入环点到相遇点的距离为 b；
环的长度为 c。
相遇时，慢指针走了 a + b；快指针走了 a + b + k·c（k 为圈数，k ≥ 1）。
因快指针速度是慢指针的2倍：2(a + b) = a + b + k·c → a + b = k·c → a = k·c - b。

此时将慢指针移到头部，两指针同速移动：

慢指针走 a 步到入环点；
快指针从相遇点走 a 步：k·c - b 步 = (k-1)·c + (c - b)，即绕 k-1 圈后，再走 c - b 步（相遇点到入环点的距离），最终也到入环点。
故二次相遇点即为入环点。

代码实现

function detectCycle(head) {
    if (!head || !head.next) return null; // 空链表或单节点无环

    // 步骤1：快慢指针判断是否有环，找到相遇点
    let slow = head;
    let fast = head;
    let hasCycle = false;

    while (fast && fast.next) {
        slow = slow.next;       // 慢指针走1步
        fast = fast.next.next;  // 快指针走2步
        if (slow === fast) {    // 相遇，有环
            hasCycle = true;
            break;
        }
    }

    if (!hasCycle) return null; // 无环，返回null

    // 步骤2：定位入环点
    slow = head;                // 慢指针移到头部
    while (slow !== fast) {     // 两指针同速移动，再次相遇即入环点
        slow = slow.next;
        fast = fast.next;
    }

    return slow; // 返回入环点
}

示例验证

示例：链表 1 → 2 → 3 → 4 → 2（入环点为 2）

判断有环：
- 慢指针路径：1 → 2 → 3 → 4
- 快指针路径：1 → 3 → 2 → 4
- 相遇于 4（假设）。
定位入环点：
- 慢指针移到头部（1），快指针在 4。
- 同速移动：
  - 慢指针：1 → 2
  - 快指针：4 → 2
- 二次相遇于 2，即入环点。

复杂度分析

时间复杂度：O(n)。
- 第一次相遇：O(n)（快慢指针最多遍历n步）。
- 第二次相遇：O(n)（两指针最多移动a + (c - b) = a + (c - b)，总长度≤n）。
空间复杂度：O(1)。仅用2个指针，无额外空间。

边界情况

无环链表：返回 null。
环起点为头节点（如 1 → 2 → 1）：二次相遇点为头节点 1。

核心思路​

原理证明​

代码实现​

示例验证​

复杂度分析​

边界情况​