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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if (pHead == nullptr || pHead->next == nullptr) {
            return nullptr;
        }
        
        // 步骤1：使用快慢指针判断是否有环
        ListNode *slow = pHead;
        ListNode *fast = pHead;
        
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            
            // 有环
            if (slow == fast) {
                // 步骤2：找到环的入口
                ListNode *ptr1 = pHead;
                ListNode *ptr2 = slow; // 或者fast，此时它们指向同一个节点
                
                // 两个指针以相同速度前进，相遇点即为环入口
                while (ptr1 != ptr2) {
                    ptr1 = ptr1->next;
                    ptr2 = ptr2->next;
                }
                
                return ptr1; // 环的入口节点
            }
        }
        
        return nullptr; // 无环
    }
};

1.慢指针在走完一圈之前一定会被快指针追上
2.数学原理
设：
链表头到环入口距离为 a
环入口到相遇点距离为 b
相遇点到环入口距离为 c
当快慢指针相遇时：
慢指针走了：a + b
快指针走了：a + b + n(b + c)（n为快指针在环中转的圈数）
由于快指针速度是慢指针的2倍：
2(a + b) = a + b + n(b + c)
化简得：a = (n-1)(b+c) + c
这意味着：从链表头到环入口的距离 = 从相遇点到环入口的距离 + (n-1)圈环长