java - 如何检测链表中的循环？

Question

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

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

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

最好的写作方式是什么

boolean hasLoop(Node first)

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

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

Answer 1

您可以使用Floyd's cycle-finding algorithm ，也称为龟兔算法。

这个想法是有两个对列表的引用并以不同的速度移动它们。一个向前移动 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;
    }
}