链表中环的入口节点

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

证明可以参考：
https://www.cnblogs.com/chengyeliang/p/4454290.html

其实可以把 i 类比为 时间

总的来说就是分两种情况：

• 两个指针在环中同一个位置出发，如果q=2p,那么必定在出发位置相遇；
• 两个指针在环中不同位置出发，如果q = 2p , 那么在 n-k 处相遇；

对于本题而言，可以先 判断是否有环（注意判断条件，p->next->next != NULL）, 并同时找到相遇节点
由于 q = 2p ,当 p 到达环的入口时（假设走了k步），q 已经在环内走了 k 步（故共走2k步）， 即 q,p起点不同，相差k步，那么二者在 n-k处相遇。 因此将p重置为开头，二者以相同的速度走，相遇时即为 入口节点

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
       if (pHead==NULL || pHead->next==NULL || pHead->next->next==NULL)return NULL;
        
        ListNode*p1 = pHead->next;
        ListNode*p2 = pHead->next->next;

        while(p2!=p1)
        {
            if (p2->next && p2->next->next)
            {
                p1 = p1->next;
                p2 = p2->next->next;
            }
            else {
                return NULL;
            }
        }
        
       // return p1;
        
        p1 = pHead;
        
        while(p1!=p2)
        {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }
};