题目描述:对于一个给定的链表,返回环的入口节点,如果没有环,返回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;
    }
    
}