链表中环的入口结点_55

    public ListNode EntryNodeOfLoop(ListNode pHead)
    {
        
        //找出环中相遇的点
        ListNode p1=pHead; //每次走一步的结点
        ListNode p2=pHead;//每次走两步的结点
        ListNode pmeet=null;
        while (p2!=null&&p2.next!=null){ //p2比p1跑的快,如果没有环的话p2先挂掉,所以只判断p2就可以了
             
            p1=p1.next;
            p2=p2.next.next;
            if (p1==p2){
                pmeet=p1;
                break;
            }
        }
        if (pmeet==null){//没环,没有相遇
            return null;
        }
        //如果有环.p1从头走,p2从相遇结点走,下一次相遇就是那个环结点.
        p1=pHead;
        p2=pmeet;
        while (p1!=p2){
            p1=p1.next;
            p2=p2.next;
        }
        return p1;
    }