力扣LCR022题解：快慢指针法检测链表环入口的完整指南

一、问题描述

给定一个链表，判断链表中是否有环，如果存在环，则返回环的起始节点（环入口），否则返回null。

二、算法核心思想

本解决方案采用经典的"快慢指针"算法，分为两个阶段：

1. 检测链表是否有环

2. 若有环则找到环的入口节点

三、完整代码实现（带详细注释）

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) return nullptr; // 空链表或单节点无环
        
        ListNode *slow = head;
        ListNode *fast = head;
        
        // 第一阶段：检测是否有环
        while (fast && fast->next) {
            slow = slow->next;       // 慢指针每次走一步
            fast = fast->next->next; // 快指针每次走两步
            
            if (slow == fast) break; // 相遇说明有环
        }
        
        // 无环情况
        if (slow != fast) return nullptr;
        
        // 第二阶段：寻找环入口
        slow = head; // 重置慢指针到头部
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        
        return slow; // 相遇点即为环入口
    }
};

四、算法分步解析

1. 边界条件处理：

• 空链表或单节点链表直接返回null

2. 第一阶段：环检测：

• 快指针每次走两步，慢指针每次走一步

• 如果相遇则说明有环

• 如果快指针到达链表末尾则无环

3. 第二阶段：环入口查找：

• 将慢指针重置到链表头部

• 快慢指针现在都每次走一步

• 再次相遇的点就是环入口

五、数学原理证明

设链表头到环入口距离为a，环入口到相遇点距离为b，相遇点到环入口距离为c 根据快指针走的路程是慢指针的两倍： 2(a+b) = a+b+n(b+c) 推导可得：a = c + (n-1)(b+c) 这意味着从链表头和相遇点同时出发，必定在环入口相遇

六、常见误区与调试技巧

1. 忘记检查fast->next是否为null导致空指针异常

2. 混淆快慢指针的移动步数

3. 不理解为什么第二阶段能找到环入口