Floyd 的循環查找演算法如何偵測鍊錶中的迴圈？

鍊錶中的高效循環檢測

檢測鍊錶中的循環是一個經典的面試問題，需要對數據結構和演算法有深入的理解。我們使用 Floyd 的循環查找演算法為這個問題提出了一個細緻的解決方案。

Floyd 的演算法使用兩個參考，一個一次前進一步，另一個一次前進兩步。這種不同的速度確保瞭如果列表中存在循環，兩個引用最終會相遇。

這裡是演算法的逐步分解：

1. 初始化兩個對清單中第一個節點的慢速和快速引用。
2. 每一步將慢速前進一個節點，快速前進兩個節點。
3. 檢查慢速或快速是否變成空。這表明不存在循環。
4. 檢查慢速和快速是否相等。如果是，則存在循環。

以下Java 函數實作Floyd 演算法：

<code class="java">public static boolean hasLoop(Node first) {

    if (first == null) // List does not exist, no loop
        return false;

    Node slow, fast; // Create two references

    slow = fast = first; // Point both 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 have a loop
            return true;
    }
}</code>

此演算法具有恆定的空間複雜度，因為它只使用兩個引用，且合理的時間複雜度為O (n)，其中n 是列表中的節點數。

以上是Floyd 的循環查找演算法如何偵測鍊錶中的迴圈？的詳細內容。更多資訊請關注PHP中文網其他相關文章！