思路:
这里可以自己画图列一下方程。
快慢指针法,快指针一次走两步,慢指针一次走一步,当快慢指针第一次相遇时
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;
}
京公网安备 11010502036488号