XingHuiSamaの宝藏之地

给定一个链表的头节点 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
解释：链表中没有环。

提示：

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

1. 算法核心思想：Floyd 判圈算法

寻找环形链表的入口节点分为两个主要阶段：

判断是否有环：利用快慢指针（双指针）。慢指针每次移动一步，快指针每次移动两步。如果链表存在环，两者必然在环内相遇。
寻找入环节点（数学推导）：设头节点到入环点的距离为 L，入环点到相遇点的距离为 x，环的周长为 C。由于相遇时快指针走过的总路程是慢指针的 2 倍，可推导出等式：L=(n−1)C+(C−x)。该等式的物理意义是：从链表头部走到入环点的距离，恰好等于从相遇点继续绕环走到入环点的距离。因此，当两指针相遇后，派出一个新指针从头部出发，与停在相遇点的慢指针以相同速度（每次一步）同步移动，两者再次相遇的位置即为入环节点。

2. 逻辑拆解

前置边界判断：在程序最开始通过 if (fast == NULL || fast->next == NULL) 拦截了长度极短且无环的链表，防止后续访问出现空指针越界。
找相遇点与 2 倍速控制：在 while (fast != NULL) 循环中，将相遇的判定 if (slow == fast) 放在了指针移动的最后。这种结构自然规避了初始状态下双指针都在头部时造成的相等误判。同时，slow 每次严格走一步，fast 通过内部的 if-else 安全地走两步，保证了严格的 2:1 速度比，从而使后续的数学推导依然成立。
无环判定与入环点查找：循环被 break 打破后，通过 if (fast == NULL) 判断打破的原因。如果是遇到 NULL，直接返回无环结果。如果是因为相遇，则声明新指针 p 从 head 出发，与 slow 进行步调一致的单步遍历，直到 p == slow，此时的重合点即为题干要求的节点。

class 环形链表II {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;

        if (fast == NULL || fast->next == NULL) {
            return NULL;
        }

        while (fast != NULL) {
            slow = slow->next;
            if (fast->next != NULL) {
                fast = fast->next->next;
            }
            else {
                fast = fast->next;
            }
            if (slow == fast) {
                break;
            }
        }

        if (fast == NULL) {
            return NULL;
        }

        ListNode *p = head;
        while (p != slow) {
            p = p->next;
            slow = slow->next;
        }

        return p;

    }
};

3. 复杂度分析

时间复杂度：O(N)。（N 为链表的节点数）。在寻找相遇点阶段，慢指针走过的距离不会超过链表的总长度；在寻找入环点阶段，两个指针移动的距离同样小于链表总长度。总体执行时间呈线性关系。
空间复杂度：O(1)。算法仅声明了 slow、fast 和 p 三个指针变量，未申请与数据规模相关的额外内存空间。