查找链表复杂性中的循环

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.next或fast.next.next.next.next？

Answer 1

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

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

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

Answer 2

当更快的指针以慢指针的两倍多的速度移动时，它可以与第一个指针重叠，而不会碰到它。如果每次两个指针通过（在同一循环内）时都会发生这种情况，则算法将为1。永远找不到循环和2。永远不要终止。

Answer 3

复杂性不以循环步骤的数量来计算，而是以访问的节点来计算。因此，上述算法只会使防止NullPointerException变得更加困难。循环也可以是任意长度的节点。

在天真解中需要二次算法：检查节点[i]没有作为所有j<i.

更快的算法使用内存。

通过生成标记（一种引用计数）作为节点的字段。

// Complexity O(N)
class Node
    Node next;
    boolean generation;
class List
    Node first;
    boolean nodesGeneration; // All nodes false or true
    boolean isCircular() {
        for (Node node = first; node != null; node = node.next) {
            if (node.generation != nodesGeneration) {
                return false;
            }
            node.generation = !node.generation;
        }
        nodesGeneration = !nodesGeneration;
        return true;
    }

或者，如果这不可能/不需要：使用以Object引用为键的IdentityHashMap。就像一组对象引用（==）。

// Complexity O(N), worse case O(N . log N)
    boolean isCircular() {
        Map<Node, Boolean> checkedNodes = new IdentityHashMap<>();
        for (Node node = first; node != null; node = node.next) {
            if (checkedNodes.containsKey(node)) {
                return false;
            }
            checkedNodes.put(node, Boolean.TRUE);
        }
        return true;
    }