剑指offer 面试题23 链表中环的入口节点

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

tips:
使用两个指针，p1 每次走1步，p2每次走2步，若有环，则p1，p2一定会重合。
然后再从重合的节点开始走一圈，记录环中节点的个数n。
再利用两个指针p1，p2, p2先走n步，直到p1,p2重合则重合的位置就是环的入口节点

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(pHead==NULL) {
            return NULL;
        }
        ListNode* p1=pHead;
        ListNode* p2=pHead;
        while(p1!=NULL&&p2!=NULL) {
            p1=p1->next;
            if(p2->next!=NULL) {
                p2=p2->next->next;
            } else {
                return NULL;
            }
            if(p1==NULL||p2==NULL) {
                return NULL;
            } else if(p1==p2) {
                // 计算环中节点的长度
                int len=2;
                p2=p2->next;
                while (p2!=p1)
                {
                    len++;
                    p2=p2->next;
                }
                // 让一个指针先走len步
                p1=pHead;
                p2=pHead;
                while (--len)
                {
                    p2=p2->next;
                }
                // 然后同时走
                while (p1!=p2)
                {
                    p1=p1->next;
                    p2=p2->next;
                }
                return p1;
            }
        }
        return NULL;
    }
};