Floyd Cycle Detection Algorithm（Floyd判圈算法），又稱Tortoise and Hare Algorithm（龜兔賽跑算法），此演算法可用來判斷LinkedList（鏈接串列）或是否存在cycle（環），並找出環的起始節點及算出cycle的長度。
此算法找出串列是否有cycle存在的方法如下：
- 使用兩個pointer（指針）t及h指向串列的起點S。t代表烏龜(tortoise)，h代表兔子(hare)。兩個指針同時向後移動，而h（兔子）移動的速度是t（烏龜）的兩倍，換句話說就是t每次移動1步（1個節點），h每次移動2步（2個節點）。
- 如果兩個指針t和h持續沿串列移動到最後沒有任何節點，代表此串列沒有cycle。
- 如果兩個指針t和h持續移動並在同個節點M相遇，代表此串列有cycle。
兩個指針t及h指向串列的起點S
兩個指針同時向後移動，而h（兔子）移動的速度是t（烏龜）的兩倍。
兩指針在同個節點M相遇表示串列存在cycle。
找出cycle起點及長度的方法如下：
- 當兩指針相遇後，把其中一個指針h重置到串列起點S，另一個指針t保持在之前兩指針相遇的節點M上。
- 接著兩指針同時開始向後移動，但此時兩指針移動的速度相同，每次都是往後1步，兩指針持續移動直到再次相遇的節點即為cycle的起始位置C。
- 保持一個指針h不動，另一個指針t每次移動1步直到兩指針再次相遇，則t的步數（經過的節點數）即為cycle的長度。
把h移至串列起點S，然後與停留在M的t同時以相同速度向後移動直到相遇的節點C即為cycle起始節點。
指針h不動，指針t每次移動1步再次遇見指針h，則t經過的節點數即為cycle的長度。
會寫這篇的原因是在Youtube看到Joma Tech - If Programming Was An Anime這部影片，蠻好笑的，然後對這算法也很好奇，上網了解後整理的結果。
沒有留言:
張貼留言