[数据结构与算法]2021-08-08

142. 环形链表 II - 力扣（LeetCode） (leetcode-cn.com)

?

①判断链表是否有环

②此时slow和fast已经相遇，设头节点到环入口的距离为x，设换入口到相遇节点的距离为y，相遇节点到环入口的距离为z

?

那么可以得出slow 走了x+y??

fast走了 x+y+(n-1)(y+z)

fast每次走两个节点，slow每次走一个

所以 （x+y）* 2 = x+y+(n-1)(y+z)

化简之后：x = (n - 1) (y + z) + z

x和z的差值就是去圈数距离的整数倍

所以当fast和slow相遇时

x和z相等

此时我们让一个节点从头出发，另外一个从相遇位置出发，相遇的位置就是环的入口

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null)return null;
        ListNode slow=head;
        ListNode fast=head;
        while(true){
            if(fast==null||fast.next==null){
                return null;
            }
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
                break;
            }
        }


        fast=head;
        while(slow!=fast){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
        
        
    }
}