思路:
这里可以自己画图列一下方程。
快慢指针法,快指针一次走两步,慢指针一次走一步,当快慢指针第一次相遇时
2(x+y)=n圈周长+x+y,
这里x+y是慢指针走的长度,n圈周长+x+y是快指针走的长度
x = n圈周长-y;
即当快指针回到head和慢指针以同样速度每次走一步,最终会在链表中环的入口结点处相遇。
public ListNode EntryNodeOfLoop(ListNode pHead) { if(pHead==null||pHead.next==null||pHead.next.next==null) return null; ListNode slow = pHead.next; ListNode fast = pHead.next.next; while(slow!=fast){ if(slow==null||fast.next==null) return null; slow = slow.next; fast = fast.next.next; } fast=pHead; while(fast!=slow){ fast=fast.next; slow=slow.next; } return fast; }