Java如何检测链表中的循环？

一尘不染

Java如何检测链表中的循环？

java

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

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

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

最好的写作方式是什么

boolean hasLoop(Node first)

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

阅读 849

2020-03-07

共1个答案

一尘不染

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

2020-03-07