环形链表检测与入口查找

题目描述

给定一个链表的头节点 head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。如果存在环，还需要找出环的入口节点（即链表开始入环的第一个节点）。这是LeetCode中“环形链表II”（#142）的经典问题。

知识背景与重要性

这是链表操作中的核心问题，考察对链表结构、快慢指针（Floyd判圈算法）的理解。在工程中，该算法可用于检测资源依赖中的循环引用、状态机中的死循环等。

解题思路：Floyd判圈算法（快慢指针法）

第一步：判断链表是否有环

1. 初始化：设置两个指针，slow（慢指针）每次移动一步，fast（快指针）每次移动两步。都从头节点 head 开始。
2. 移动与判断：在循环中，每次移动 slow 一步，fast 两步。
   • 如果 fast 或其 next 为 null，说明链表无环，可以返回 null。
   • 如果 slow 和 fast 相遇，则链表一定有环。此时进入第二步。

原理：想象两个人在环形跑道上跑步，快的人速度是慢的人的两倍。他们从同一起点出发，因为跑道是环形的，快的人最终一定会从后面追上慢的人（即相遇）。

第二步：寻找环的入口

1. 定位相遇点：第一步结束后，slow 和 fast 在环内某点相遇。
2. 重置指针：将一个指针（例如 ptr1）重新指向链表头 head，另一个指针 ptr2 保持在相遇点。
3. 同步移动：两个指针都改为每次移动一步。当它们再次相遇时，相遇点即为环的入口节点。

原理解析（需要一点数学推导）：

• 设链表头到环入口的距离为 F，环入口到第一步中相遇点的距离为 a，相遇点再回到环入口的距离为 b，那么环的周长 C = a + b。
• 第一步相遇时：
  • slow 指针走过的距离为 F + a。
  • fast 指针走过的距离为 F + a + n*C，其中 n 是 fast 在环内绕的圈数（n >= 1）。
  • 因为 fast 速度是 slow 的两倍，所以有：2(F + a) = F + a + n*C。
  • 化简得：F = n*C - a = (n-1)*C + b。
• 第二步同步移动：
  • ptr1 从 head 出发走 F 步到达入口。
  • ptr2 从相遇点出发，走 F 步。根据上式 F = (n-1)*C + b，ptr2 先走 b 步到达入口，再绕 (n-1) 圈，最终也停在入口。因此两者在入口处相遇。

代码实现（Java）

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode slow = head;
        ListNode fast = head;

        // 第一步：判断是否有环
        while (fast != null && fast.next != null) {
            slow = slow.next;       // 慢指针走一步
            fast = fast.next.next;  // 快指针走两步

            if (slow == fast) { // 相遇，说明有环
                // 第二步：寻找环的入口
                ListNode ptr1 = head;
                ListNode ptr2 = slow; // 也可以使用fast，此时它们位置相同
                while (ptr1 != ptr2) {
                    ptr1 = ptr1.next;
                    ptr2 = ptr2.next;
                }
                return ptr1; // 返回环的入口节点
            }
        }
        // fast遇到null，说明无环
        return null;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

复杂度分析

• 时间复杂度：O(N)。在第一步中，slow 指针在相遇前最多走 F + a 步（小于链表总长度）。第二步中，两个指针最多走 F 步。总体是线性复杂度。
• 空间复杂度：O(1)。只使用了几个固定数量的指针变量。

关键点总结

1. 核心思想：快慢指针是解决环形链表问题的标准且最优方法。
2. 相遇一定有环：在有环链表中，快指针不会“跳过”慢指针，因为它们的速度差是1。
3. 入口公式推导：理解 F = (n-1)*C + b 是理解算法为何第二步能定位入口的关键。
4. 边界条件处理：注意处理空链表、单节点无环等情况。