什麼是解決循環鏈表的方法？

Question

給定一個循環鏈表，給出一個在循環開始時返回節點的算法。

定義： 特定鏈接列表：一個（損壞的）鏈接列表，其中一個節點的下一個指針指向一個較早的節點，以便在鏈接列表中創建一個循環。

實施例： 輸入：A-> B-> C-> D-> E-> C [相同的C如前面] 輸出：C

Answer 1

可以使用tortoise and the hare algortihm：

1. 開始用兩個指針，調用一個tortoise和其他hare
2. 在每個時間步，推進烏龜一次，兩次野兔
3. 重複，直到它們相等

這給你一個循環內的元素。要找到循環的開始：

1. 提前烏龜一步一個時間，計算步驟
2. 停止數，直到你到達野兔

這將讓你找到循環的長度。然後你只需要步驟size-length來查找開始，其中size是「鏈接列表」中元素的數量。

這也被稱爲弗洛伊德的循環檢測算法。

Answer 2

檢測通常的算法循環是讓兩個指針/迭代器在列表中前進一個元素，而另一個元素則一次前進一個元素。如果兩個迭代器指向同一個元素，則列表中有一個循環。

找到循環後，您可以收集集合中的所有元素，然後從列表的開始處開始，直到找到該集合中的元素。這個元素可以被認爲是循環的「開始」

Answer 3

最簡單的算法是使用數據結構來存儲已訪問過的元素。您可以使用散列表（大約O（n））或簡單的排序數組O（nlog（n））。

你也可以假設你的鏈表是一個圖表，並使用cycle detection常用的算法之一。