链表中环的入口结点

题目：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解题思路

1、设快慢指针，当快慢指针相遇时，快指针走的长度刚好是慢指针的两倍

2、快慢指针一定在环中相遇，而且第一次相遇慢指针一定还没绕环超过一圈，因为当慢指针进入环时，此时快指针无论在环中的哪个位置，都可以在慢指针走一圈之内追上。

3、可以设快慢指针在A点相遇，那么慢指针走过的长度位x1+x2,而快指针走过的长度为x1+x2+nL,其中L为圆环的长度,n为整数。当快慢指针相遇时，快指针走过的长度刚好是慢指针的两倍，则2(x1+x2)=x1+x2+nL,也就是x1+x2=nL。当快慢指针相遇在点A时，让新指针指向链表头和慢指针同步一步一步走，则他们刚好在入口处相遇。因为此使新指针刚好走了x1，而慢指针则刚好走了nL-x2。

代码如下：

class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        ListNode *p,*q,*n;
        p = pHead;//快指针
        q = pHead;//慢指针
        while(p!=NULL && p->next!=NULL){
            p = p->next->next;
            q = q->next;
            if (p == q)
            {
                n = pHead; //新指针
                while(n != q){
                    n = n->next;
                    q = q->next;
                }
                return q;
            }
        }
        return NULL;
    }
};