如何检测链表中的循环？

algorithm data-structures java linked-list

2022-08-31 04:28:24

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

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

并且每个节点都指向下一个节点，但最后一个节点除外，该节点的下一个节点为 null。假设列表可能包含一个循环 - 即最终节点，而不是具有空值，具有对列表中位于其前面的节点之一的引用。

最好的写作方式是什么

boolean hasLoop(Node first)

如果给定的节点是具有循环的列表的第一个，这将返回，否则？你怎么能写得需要恒定的空间和合理的时间？truefalse

下面是带有循环的列表的外观图片：

alt text

答案 1

您可以使用弗洛伊德的循环查找算法，也称为和野兔算法。

这个想法是让两个引用到列表，并以不同的速度移动它们。按节点向前移动一个，按节点向前移动另一个。12

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

实现算法的 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;
    }
}

答案 2

以下是快速/慢速解决方案的改进，该解决方案可正确处理奇数长度列表并提高清晰度。

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
}