142. 环形链表 II

image.png

要求出环形链表的起始点
难点在于如何推出起始点的位置
首先假设链表的长度为b，其余长度为a

image.png
image.png

关键：走到起始点,必须走a+nb步，第一次相遇nb。所以我们让fast从头开始走a步，就会与慢指针第二次相遇
注意是第二次相遇，但不是最后一次相遇
下一次相遇可能在下一个节点，不一定是在入口节点

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null) return null;
        ListNode fast=head;
        ListNode slow=head;
        while(fast.next!=null&&fast.next.next!=null){
            
            fast=fast.next.next;
            slow=slow.next;
            if(slow==fast) break;
        }
        if(fast.next==null||fast.next.next==null) return null;//如果没有环，这一步就退出来了，不会继续处理下边///的代码
        
        fast=head;
        while(fast!=slow){//因为有环，就不用再去判断fast.next，因为肯定能一直走下去
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
}