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

使用快慢指针解决问题。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        /*-----------------*/
        /*判断pHead是否为空*/
        /*-----------------*/
        if(pHead==nullptr)return nullptr;
 
        /*----------------*/
        /*   创建快慢指针  */
        /*----------------*/
        ListNode* fast=pHead,*slow=pHead;
 
        /*----------------------------------*/
        /*判断fast和fast->next是否遇到链表尾*/
        /*-----------------------------------*/
        while(fast && fast->next){
            /*-------------------------*/
            /*慢指针走一步，快指针走两步*/
            /*-------------------------*/
            slow=slow->next;
            fast=fast->next->next; 
            /*--------------------*/
            /*判断快慢指针是否相遇*/
            /*--------------------*/
            if(fast==slow){
                slow=pHead;
                /*--------------------------------------*/
                /*当head和meet相遇，说明遇到环的起始位置*/
                /*--------------------------------------*/
                while(slow!=fast){
                   slow=slow->next;
                   fast=fast->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};