142-环形链表-ii

struct ListNode {
    int val;
    ListNode* next;

    ListNode(int x)
        : val(x),
          next(NULL) {}
};

ListNode* detectCycle(ListNode* head) {
    // 如果环存在 当 slow 到达环的起点时， fast 肯定在环中某个位置,而且至少在环中走了一整圈
    // 环中走 1 圈和 n 圈到达的位置和是一样的，所以走多少圈效果不变,L 为圈长，则 nL == L
    // 那么第一次相遇 fast 在环里 走了 L + y，fast 走了 L + y + x， slow 走了 x + y
    // 而 fast = 2 slow  ==> 2(x + y) = L + x + y
    // x + y = L ==> x = L - y

    ListNode* slow = head;  // 慢指针一次走一步
    ListNode* fast = head;  // 快指针一次走两步
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {  // 相遇
            ListNode* p = head;

            while (p != slow) {  // x = L - y
                p    = p->next;
                slow = slow->next;
            }

            return p;
        }
    }
    return nullptr;
}