如何检测链表中的循环？

Question

假设您在 Java 中有一个链表结构。它由节点组成：

 class Node {
    Node next;
    // some user data
}

每个 Node 都指向下一个节点，除了最后一个 Node，它的 next 为 null。假设列表有可能包含一个循环 - 即最终节点，而不是空值，具有对列表中在它之前的节点之一的引用。

最好的写作方式是什么

boolean hasLoop(Node first)

如果给定的节点是带有循环的列表的第一个，它将返回 true ，否则返回 false ？你怎么能写出来，让它占用恒定的空间和合理的时间？

这是带有循环的列表的图片：

原文由 jjujuma 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您可以利用 Floyd 的寻环算法，也称为 _龟兔算法_。

这个想法是有两个对列表的引用并以 不同的速度 移动它们。将一个向前移动 1 节点，另一个向前移动 2 节点。

• 如果链表有循环，它们 肯定会 相遇。
• 否则，两个引用中的任何一个（或它们的 next ）将变为 null 。

实现算法的Java函数：

 boolean hasLoop(Node first) {

    if(first == null) // list does not exist..so no loop either
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer to the start of the list

    while(true) {

        slow = slow.next;          // 1 hop

        if(fast.next != null)
            fast = fast.next.next; // 2 hops
        else
            return false;          // next node null => no loop

        if(slow == null || fast == null) // if either hits null..no loop
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop
            return true;
    }
}

原文由 codaddict 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

这是 Fast/Slow 解决方案的改进，它可以正确处理奇数长度列表并提高清晰度。

 boolean hasLoop(Node first) {
    Node slow = first;
    Node fast = first;

    while(fast != null && fast.next != null) {
        slow = slow.next;          // 1 hop
        fast = fast.next.next;     // 2 hops

        if(slow == fast)  // fast caught up to slow, so there is a loop
            return true;
    }
    return false;  // fast reached null, so the list terminates
}

原文由 Dave L. 发布，翻译遵循 CC BY-SA 2.5 许可协议