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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
  public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* fast = pHead, *slow = pHead;
        // 1. 找到相遇点
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)  break;
        }
        // 2.没到找相遇点，就返回nullptr
        if (fast == nullptr || fast->next == nullptr)  return nullptr;
        // 快指针走x + n(y+z) + y 慢指针走 x + m(y+z) + y
        // x+y = (n-2m)(y+z) 即，链表头到相遇位置的距离是环距离的整数倍
        // 那么一个指针从链表头开始 另一个从相遇位置开始 会同时走到相遇位置，而在走到相遇位置前，都会同一时刻经过环的入口节点
        ListNode* res = pHead;
        while (res != slow) {
            res = res->next;
            slow = slow->next;
        }
        return res;
    }
};