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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
/*从相遇点出发和从起点出发的相遇结点就是入口结点*/
class Solution {
  public:
    ListNode* hasCycle(ListNode* pHead) {
        if (pHead == nullptr) {
            return nullptr;
        }
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        while (fast != nullptr && fast -> next != nullptr) {
            fast = fast -> next -> next;
            slow = slow -> next;
            if (fast == slow) {
                return fast;
            }
        }
        return nullptr;
    }
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* l1 = hasCycle(pHead); // linked-list-1
        if (l1 == nullptr) {
            return nullptr;
        }
        ListNode* l2 = pHead;
        while (l1 != l2) {
            l1 = l1 -> next;
            l2 = l2 -> next;
        }
        return l1;
    }
};

从相遇点出发和从起点出发的相遇结点就是入口结点