题解 | 链表中环的入口结点

/*
 * 环形链表入口检测算法（Floyd判圈算法）
 * 原理说明：
 * 1. 快慢指针首次相遇时，快指针走过的距离是慢指针的2倍
 * 2. 设头节点到环入口距离为a，环入口到相遇点距离为b，环长为c
 *    则有：a + b = n*(b + c) + b → a = n*c + (n-1)*b + c
 *    化简得：a = (n-1)*(b + c) + c → 头节点到入口的距离等于相遇点到入口的距离（绕环n-1圈后）
 * 3. 重置一个指针到头部，两个指针同步移动，再次相遇即为入口节点
 */

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}  // 构造函数初始化节点
};

class Solution {
public:
    /**
     * @brief 检测链表是否有环并返回相遇节点
     * @param head 链表头节点
     * @return 相遇节点指针（无环返回nullptr）
     * 
     * 算法步骤：
     * 1. 初始化快慢指针到头部
     * 2. 快指针每次移动两步，慢指针移动一步
     * 3. 当指针相遇时返回相遇点
     * 4. 遍历结束未相遇则说明无环
     */
    ListNode* detectIntersection(ListNode *head) {
        // 处理空链表或单节点无环情况
        if (!head || !head->next) return nullptr;
        
        ListNode *slow = head, *fast = head;  // 初始化快慢指针
        
        // 快指针先移动两步，确保两个指针不同步
        while (fast && fast->next) {
            slow = slow->next;          // 慢指针每次移动一步
            fast = fast->next->next;    // 快指针每次移动两步
            
            // 首次相遇点即为环内某节点
            if (slow == fast) return slow;  
        }
        return nullptr;  // 未相遇说明无环
    }

    /**
     * @brief 找到环形链表的入口节点
     * @param pHead 链表头节点
     * @return 环入口节点指针（无环返回nullptr）
     * 
     * 算法步骤：
     * 1. 调用detectIntersection获取相遇节点
     * 2. 无环则直接返回nullptr
     * 3. 重置一个指针到头部，另一个保持在相遇点
     * 4. 两个指针同步移动，再次相遇即为入口节点
     */
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        // 获取快慢指针相遇点
        ListNode *meetNode = detectIntersection(pHead);
        if (!meetNode) return nullptr;  // 无环处理
        
        // 重置指针到头部
        ListNode *ptr1 = pHead;
        ListNode *ptr2 = meetNode;
        
        // 同步移动直到再次相遇（入口节点）
        while (ptr1 != ptr2) {
            ptr1 = ptr1->next;  // 头指针每次移动一步
            ptr2 = ptr2->next;  // 相遇点指针每次移动一步
        }
        return ptr1;  // 返回环入口节点
    }
};