查找鏈接列表中循環的開始節點？

Question

如何查找給定鏈表中循環的開始節點？我們到目前爲止，稱其爲週期來看

，我已經明白了以下（使用快/慢指針）：

1. 假設列表中有大小k
2. 緩慢的非循環部分移動k步
3. 快速移動2K步驟
4. 快（2K - K）= k步驟的緩慢
5. ahead慢是在循環的開始;也被稱爲Cycle point
6. 快是(LOOP_LENGTH - k)此時
7. 每次1步緩慢移動時，快速移動2步和增益上緩慢通過1步的步從Cycle point或慢指針behind。
8. 因此，將採取快速(LOOP_LENGTH - k)措施，以滿足慢，碰撞
9. 這是一步我不明白： 在此碰撞點，兩個節點會從循環的前k步驟。
10. 找到碰撞點後，將一個指針移動到列表頭部。
11. 現在以1步/轉的速度移動兩個指針直到碰撞。他們都遇到的節點是循環的開始，因此Cycle point

有人可以解釋我第9步，然後呢？

感謝

編輯：

有一兩件事我想指出的是，一旦循環裏面，快速的將永遠不會超過慢指針。他們會碰撞。這就是爲什麼：慢我在，我快速假設在I - 1。當他們移動時，slow => i + 1並且fast也會在i + 1上，因此碰撞。或者，我速度很慢，速度很快，在i-2。下一步，慢 - > i + 1;快：我。下一步，慢 - >我+ 2，快：我+ 2，因此再次碰撞。如此之快的速度永遠無法超越緩慢，只會在循環內碰撞一次！

Answer 1

你6是錯誤的，快速的指針仍然k步距緩慢的指針，是在當時的週期點;但更好的利用提前或背後，而不是遠離。另外，k可能會更小，更大或等於loop_length。

所以，快速指針是k10前一個緩慢的一個，當它達到循環點，這是在你的假設，k步驟開始後。現在，在一個循環上測量，快速指針在循環點前面k % loop_length步。對？如果k = some_n * loop_length + r，快速指針是未來的循環點，這是說，提前r := k % loop_length步驟r步驟。

但是，這意味着緩慢的指針loop_length - r步驟領先快一的，沿着循環。畢竟這是一個循環。因此，在loop_length - r附加步驟後，快速指針將捕捉到較慢的指針。對於每一步慢速指針移動，快速移動靠近兩個步驟步驟。

所以我們不知道k，我們不知道loop_length或r，我們只知道m = k + loop_length - r = some_n * loop_length + r + loop_length - r = (some_n+1) * loop_length。直到兩個指針的會合點的步驟總數爲m，是循環長度的倍數。

所以現在我們重新開始，以在開始和緩慢的一個新的指針在那裏遇見未來的新的快速，m步驟。我們以相同的速度移動新的和慢的，每次移動1步，並且在他們將要遇到的循環點 - 因爲當新的指針到達循環點時，第二個仍然是前面的步驟，也就是說，沿着循環前進m % loop_length == 0步。這樣我們就可以找出k是什麼（我們一直都在計數我們的步數）和循環點。

我們沿一個有更多的時間去，直到兩人見面一次發現loop_length。

• 還看到：http://en.wikipedia.org/wiki/Cycle_detection#Algorithms

Answer 2

嗯..這種問題很難解釋，除非你正在面對面地交談。我會試一試。

首先在步驟6：我認爲快速指針應距離圓點的距離爲k。

但留下所有。我們現在有兩輛車。一輛速度超過慢車速度兩倍的快車。

假設快車從圓點開始在圓軌道k的距離處。

慢車從圓點開始。

現在我要說的是兩車將在k距離滿足圓圈點之前。

爲什麼？因爲最初的快車距離圓點的距離是k。快車在第一次完成時會覆蓋n距離。現在這輛快車又離圓點k點距離。但慢車距離圓點的距離爲n/2。

現在的快車已經覆蓋了n-2k的距離，更遠達到了k之前的距離。而慢車必須覆蓋n/2 - k = (n-2k)/2距離才能達到k距離的起點。 Which is exactly half the distance of the path to be covered by the fast car。快車的速度是慢車的兩倍。

所以，很顯然，他們將在距離圓點k距離之前滿足。