Floyd 算法如何检测链表中的循环？

使用 Floyd 算法检测链表中的循环

确定给定链表是否包含循环在 Java 编程中是一项具有挑战性的任务。当列表中的最后一个节点引用前一个节点而不是空引用时，就会发生循环。

为了有效地检测循环，开发人员经常使用 Floyd 的循环查找算法，也称为龟兔赛跑算法。该算法使用两个引用，一个慢速引用和一个快速引用，以不同的速度遍历列表。

例如，慢速引用前进一个节点，而快速引用前进两个节点。如果链表包含循环，这些引用最终会相遇。另一方面，如果没有循环，则慢引用或快引用（或它们的后续引用）将在另一个到达列表末尾之前变为 null。

这是 Floyd 算法的 Java 实现:

<code class="java">boolean hasLoop(Node first) {
    if (first == null) {
        return false; // List does not exist, so no loop
    }

    Node slow, fast; // Create two references.
    slow = fast = first; // Make both refer to the start of the list.

    while (true) {
        slow = slow.next; // One hop.

        if (fast.next != null) {
            fast = fast.next.next; // Two hops.
        } else {
            return false; // No loop.
        }

        if (slow == null || fast == null) {
            return false; // No loop.
        }

        if (slow == fast) {
            return true; // Loop detected.
        }
    }
}</code>

该算法的空间复杂度为 O(1)，运行时间为 O(n)，因此既节省内存又相当耗时。

以上是Floyd 算法如何检测链表中的循环？的详细内容。更多信息请关注PHP中文网其他相关文章！