在链表复杂性中寻找循环？

Question

在链表中找到循环的正常场景是移动一个指针一次，移动另一个指针两次。如果它们相遇，则链表中存在一个循环。

但是如果我移动第二个指针三四次会发生什么。它会降低复杂度吗？为什么我们只需要移动第二个指针两次。

boolean hasLoop(Node first) {
    Node slow, fast; 
    slow = fast = first; 
    while(true) {
        slow = slow.next; 
        if(fast.next != null)
            fast = fast.next.next; 
        else
            return false;  

        if(slow == null || fast == null) 
            return false;

        if(slow == fast) 
            return true;
    }
}

而不是 fast.next.next，为什么我不能有 fast.next.next.next 或 fast.next.next.next.next.next？

Answer 1

由于快指针的移动速度是慢指针的两倍，因此两个指针之间的距离总是增加 1（最初它们之间的距离是 2）。

现在假设循环存在并且当慢指针进入循环时，慢和快之间的距离是“x”，循环的长度是“d”。所以现在下一次慢速和快速移动时，它们之间的距离将变为 x+1，然后在下一步移动时将变为 x+2，然后是 x+3，依此类推。只要它们之间的距离是 d 的倍数，快和慢就会相遇。因此，通过将它们之间的距离增加 1，我们正在检查每个值。

现在考虑快速移动三倍的情况，那么它们之间的每一步距离都会增加 2，即 x、x+2、x+4 等等。因此，这两个指针可能不会相遇并相互交叉，如果发生这种情况，您的程序将永远不会终止。如果快速指针的速度是四倍，五倍等，情况类似。