確定給定鍊錶是否包含循環在 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中文網其他相關文章！
