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

如图：①处是环的入口，②处是快指针与慢指针相遇的地方。相遇时，慢指针走过的节点数是x+y，快指针走过的节点数是x+y+n(y+z)，即相遇之前，快指针可能在环里绕了n圈（n>=1）。又因为快指针走过的节点数是慢指针的2倍，所以有：

(x+y)2=x+y+n(y+z)

x+y=n*(y+z)

x+y=(n-1)*(y+z)+y+z

x=(n-1)*(y+Z)+z

所以可以得到，让一个指针1从链表开始处走，另一个指针2从②处开始走，都以一个单位走，最后两者相遇处就是环的入口，这个过程中，指针2会在环里绕（n-1）圈。n≥1

代码如下：

```/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if(pHead==nullptr||pHead->next==nullptr)
            return nullptr;
        ListNode* slow=pHead;//先定义快慢指针，找到位置②
        ListNode* fast=pHead;
        while(fast!=nullptr&&fast->next!=nullptr)
        {
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast){
                break;
            }
        }
        if(fast==nullptr||fast->next==nullptr)
            return nullptr;
        
        ListNode* start=pHead;//从链表头部出发一个指针
        while(start!=slow){
            start=start->next;//链表头部出发的指针
            slow=slow->next;//从②处出发的指针
        }
        return start;

    }
};