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

//参考了剑指offer上讲解的快慢指针法。核心思路分3步：
//1.先确定有无环：快指针一次走2步，慢指针走1步，发生重逢说明有环。
//2.确定环的长度：重逢一定是在环中发生的，从重逢的位置开始，用个temp一直往前推进，直到回到这个位置，记录这个过程中走了多少步，这就是环的长度。
//3.移动到环开始的位置：让快指针从head开始走n步（n为环长度），相当于让慢指针落后n步，这样当快指针绕环走完一圈回来后正好能赶上慢指针刚抵达环的开头。
class Solution {
public:
    ListNode* HasLoop(ListNode* p)
    {
        if(p==nullptr)
        {
            return nullptr;
        }
        ListNode* slow=p;
        ListNode* fast=p;
        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* OneNodeInLoop=HasLoop(pHead);//找到环中的某一个节点。
        if(OneNodeInLoop==nullptr)
            return nullptr;
        ListNode* temp=OneNodeInLoop;
        int LoopLength=0;//环的长度。
        do {
            temp=temp->next;
            LoopLength++;
        }while(temp!=OneNodeInLoop);
        ListNode* slow=pHead;
        ListNode* fast=pHead;
        for(int i=LoopLength;i>0;i--)
        {
            fast=fast->next;//先将fast往前挪n步，n为环的长度。也可以理解为让slow少走一个环的距离，这样在fast绕环走完一圈后，slow才刚好赶到，这样就正好重合了。
        }
        while (fast!=slow) {//让slow与fast同速前进，直到重逢
            fast=fast->next;
            slow=slow->next;
        }
        return fast;
    }
};