🔗 环形链表 II：寻找环的入口

题目来源：142. 环形链表 II – 力扣（LeetCode）

---

📌 题目描述

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

• 不允许修改链表结构。
• 不能使用额外的哈希表存储节点。

⚠️ 注意：输入中的 pos 仅用于标识环的起始位置，不作为参数传入函数。

---

✅ 示例解析

示例 1：

• 输入：head = [3,2,0,-4], pos = 1
• 输出：返回值为索引 1 的节点（即值为 2 的节点）
• 解释：链表尾部（-4）连接到索引为 1 的节点，形成环。

示例 2：

• 输入：head = [1,2], pos = 0
• 输出：返回值为索引 0 的节点（即头节点 1）
• 解释：尾部连接到头节点，形成环。

示例 3：

• 输入：head = [1], pos = -1
• 输出：null
• 解释：无环。

---

⚠️ 提示

• 链表中节点的数目范围在 [0, 10⁴] 内
• -10⁵ <= Node.val <= 10⁵
• pos 的值为 -1 或链表中的一个有效索引

---

💡 解法：快慢指针 + 数学推导 —— O(n) 时间，O(1) 空间

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break; 
            }
        }
        if (fast == null || fast.next == null) {
            return null; 
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

---

📊 复杂度分析

• 时间复杂度：O(n)
  • 第一阶段找相遇点：O(n)
  • 第二阶段找环入口：O(n)
  • 总体线性时间。
• 空间复杂度：O(1) ✅
  • 仅使用两个指针，无额外空间。

---

🧩 解题思路

1. 核心思想：快慢指针相遇 + 数学推导定位入口
   • 第一步：使用Floyd 判圈算法（快慢指针）判断是否有环。
   • 第二步：若存在环，利用距离关系找到环的入口节点。
2. 数学推导（关键！） 设：
   • a：从头节点到环入口的距离。b：从环入口到快慢指针第一次相遇点的距离。c：从相遇点绕环回到入口的距离（即环剩余部分）。环总长：b + c。
   当快慢指针相遇时：
   • slow 走了：a + b fast 走了：a + b + c + b = a + 2b + c（因为 fast 可能绕环多走了一圈）
   由于 fast 速度是 slow 的 2 倍：2(a + b) = a + 2b + c => 2a + 2b = a + 2b + c => a = c结论：从头节点到环入口的距离 a，等于从相遇点到环入口的距离 c！
3. 如何利用 a = c 找到入口？
   • 将 slow 指针重置到头节点 head。
   • fast 指针保持在相遇点。
   • 两个指针都每次走一步。
   • 当它们再次相遇时，相遇点就是环的入口。
   因为：
   • slow 从头走 a 步 → 到达入口。
   • fast 从相遇点走 c 步 → 也到达入口（因为 a = c）。
4. 举例说明： 对 head = [3,2,0,-4]，环连接到 2（索引 1）：
   • 第一阶段：fast 和 slow 在 -4 处相遇（假设）。
   • a = 1（3 → 2）
   • b = 2（2 → 0 → -4）
   • c = 1（-4 → 2）
   • 推导得 a = c = 1。
   • slow 从 3 出发，fast 从 -4 出发，各走 1 步：
     • slow 到 2，fast 到 2 → 相遇！返回 2 ✅
5. 边界处理：
   • 空链表：fast == null → 返回 null。
   • 单节点有环：head.next = head → 第一阶段 fast == slow → slow = head → while(slow != fast) 不执行 → 返回 head ✅