剑指offer23:链表中环的入口地址

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

思路：链表存在环，则没有尾节点. 对于链表一个指针无法解决时，考虑使用两个指针，当使用两个指针分别从头节点出发，一个一次走一步，一个一次走两步，若存在环，走两步的必定能绕环一圈追上走一步的. 当追上时，从其中一个出发绕环一圈回到出发点，可得到环的节点数k. 入口节点：同上使用两个指针，一个先走k步，然后两者同时往后走，当二者指向同一节点时即为环的入口节点.

int IsLoop(ListNode* root){//判断是否存在环，返回环中节点数
        ListNode* p1=root;
        ListNode* p2=root;
        int result=1;
        while(p2!=nullptr){
            p1=p1->next;
            p2=p2->next;
            if(p2==nullptr)
                return -1;
            p2=p2->next;
            if(p1==p2){
                p2=p2->next;
                while(p1!=p2){
                    result++;
                    p2=p2->next;
                }
                return result;
            }
        }
    }
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(pHead==nullptr)
            return nullptr;
        int length = IsLoop(pHead);
        if(length==-1)
            return nullptr;
        ListNode* p1=pHead;
        ListNode* p2=pHead;
        while(length){
            p2=p2->next;
            length--;
        }
        while(p1!=p2){
            p1=p1->next;
            p2=p2->next;
        }
        return p1;
    }