题目描述:对于一个给定的链表,返回环的入口节点,如果没有环,返回null
快慢指针方法:将两指针分别放在链表头(X)和相遇位置(Z),并改为相同速度推进,则两指针在环开始位置相遇(Y),如图所示。
证明过程:X,Y,Z分别为链表起始位置,环开始位置和两指针相遇位置,由快指针速度的慢指针速度的2倍。
快指针与慢指针均从X出发,在Z相遇。此时,慢指针行使距离为a+b,快指针为a+b+n(b+c)。
所以2*(a+b)=a+b+n*(b+c),推出
a=(n-1)*b+n*c=(n-1)(b+c)+c;
得到,将此时两指针分别放在起始位置和相遇位置,并以相同速度前进,当一个指针走完距离a时,另一个指针恰好走出 绕环n-1圈加上c的距离。
public class Solution{ public ListNode detectCycle(ListNode head){ ListNode slow=head; ListNode fast=head; while(fast!=null&&fast.nest!=null){ fast=fast.next.next slow=slow.next; if(fast==slow){ //利用快慢指针找相遇点 ListNode slow2=head; //设置以相同速度的新指针从起始位置出发 while(slow2!=slow){ //未相遇循环。 slow=slow.next; slow2=slow2.next; } return slow; } } return null; } }