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

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if(pHead->next==pHead) return pHead;  //单个元素成环直接返回头节点
        if(pHead->next==NULL) return NULL;   //只有一个元素不成环，直接返回null
        ListNode* fast=pHead->next->next;  //定义快指针一次走两个
        ListNode* slow=pHead->next;           //定义慢指针一次走一个
        while(fast!=slow){                //如果表中有环则二者必定在慢指针走完环一圈前相遇
            if(fast==NULL) return NULL;    //在fast前进的过程中，只要fast=null，则表明表中无环
            fast=fast->next;
            if(fast==NULL) return NULL;
            fast=fast->next;
            slow=slow->next;
        }
        fast=pHead;          //此时快慢指针指向环中的同一个节点，此时令慢指针保存，快指针回到头
        while(fast!=slow){        //令快慢指针速度相同往后走，当他们相遇时，就是第一个入环的节点
            fast=fast->next;
            slow=slow->next;
        }
        return fast;        //此时返回fast或slow都可
    }
};

/*
原理解释 
    考虑表中确实有环的情况，快慢指针首次相遇时，慢指针走过的路程时进环前的a和环内的b
    而快指针走过的路程是环前的a+环内的b+除b外剩下环的部分c+第二圈走过的b
    而此时快指针走过的路程是慢指针的2倍
    所以可以得到a+b+b+c=（a+b）*2   所以a=c，即环前的路程和当前相遇位置再走到环入口的路程相同
    所以此时令一个指针回到链表头，二者同速前进到相遇，就恰好是环入口，返回即可。
*/