檢測鍊錶中的循環

另一種鍊錶演算法。

偵測鍊錶中的循環。

這其實並沒有那麼糟。至少有 3 種不同的方法可以實現 O(n) 時間。

最簡單的方法需要修改鍊錶節點以包含一個表示節點是否已被存取的標誌。在遍歷清單的過程中，如果遇到已經造訪過的節點，則存在循環。

另一種技術使用包含訪問過的節點或對它們的引用的雜湊圖。當列表被遍歷時，節點或其引用被插入到雜湊中。如果我們遇到一個已經在哈希圖中表示的節點，則存在循環。雖然這種技術只需要一次遍歷，但由於哈希圖，它確實需要更多記憶體。

在這篇文章中，我將使用 Floyd 演算法來偵測循環。很簡單。

func DetectCycle[T any](ll *LinkedList[T]) bool {
    slow := ll.Head
    fast := ll.Head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if fast == slow {
            return true
        }
    }
    return false
}

此技術使用 2 個指向清單的指標。當遍歷列表時，一個指標一次移動一個節點，另一個指標一次移動兩個節點。如果兩個指標相遇，則存在循環。

為什麼會這樣？隨著清單的遍歷，兩個指針之間的距離增加。如果存在循環，快指針會「一圈」慢指針。

有沒有更有效率的實作方式？是否缺少任何邊界條件？請在評論中告訴我。

謝謝！

這篇文章以及本系列所有文章的程式碼可以在這裡找到

以上是檢測鍊錶中的循環的詳細內容。更多資訊請關注PHP中文網其他相關文章！