剑指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;
    }