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中文網其他相關文章！