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

  • Z时代
  • 2024-01-10
  • 分类：问答

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

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

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

最好的写作方式是什么

boolean hasLoop(Node first)

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

回答：

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

以上是 Java如何检测链表中的循环？ 的全部内容， 来源链接： utcz.com/qa/428815.html

回到顶部