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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
#include <cstdio>
class Solution {
  public:
    ListNode* FindCrossNode(ListNode* pHead)
    {
        if (pHead == nullptr) {
            return nullptr;
        }
        ListNode* pFast = pHead;
        ListNode* pSlow = pHead;
        while ((pFast != nullptr) && (pSlow != nullptr) && (pFast->next != nullptr)) {
            pFast = pFast->next->next;
            pSlow = pSlow->next;
            if (pFast == pSlow) {
                return pFast;
            }
        }
        return nullptr;

    }

    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        // 找汇合点
        if (pHead == nullptr) {
            return nullptr;
        }
        auto pCrossNode = FindCrossNode(pHead);
        if (pCrossNode == nullptr) {
            return nullptr;
        }
        // 从起始点到交汇点的距离是环长度的整数倍，即两个指针均单步遍历的话，
        // 从起始点到交汇点和从交汇点到交汇点可以相遇（环中可能已经走了若干圈），
        // 由于从入口点到交汇点之间是重合部分，则在入口点就是第一个相遇点
        
        while ((pHead != pCrossNode)) {
            pHead = pHead->next;
            pCrossNode = pCrossNode->next;
        }
        return pHead;
    }
};