該文章內容於2020/9/13更新，若需要閱讀舊版內容，可以參照以下連結：https://hackmd.io/@eklipsorz/By-12SsEP
當你想解決任何一個需要檢測在多個相互連接的元素是否存在著循環結構之場景，比如說
- 道路模型。
- 由多個有限狀態所組成的數學模型。
- 有限輸入下在同一個函式f(x)所形成的結果，比如集合為{1,2}，且f(1)=2以及f(2)=1，在這裏1和2就透過函式關係形成一個環狀結構。
我們可以將這些場景轉化成由多個節點構成的List結構，並且大致區分為兩種不同結構：
- 擁有循環結構的List結構
2. 沒擁有循環結構的List結構
當我們轉換成如此的結構時，我們可以更容易以肉眼看出哪些模型存在著循環，在這裏我們可以知道List A是存在著循環，而List B由於尾巴部分並未跟 前幾個節點相接，所以不構成循環。在這裡你或許會選擇以肉眼來辨識，但現實是當面對大量或者複雜的模型時，肉眼看會顯得效率太差，所以最好由電 腦進行這樣的重複辨識工作。
可換作是電腦，它要如何辨識呢？畢竟他本身就不存在像人眼那樣的辨識模型，在這裏提供一個方法來幫助電腦辨識：Floyd’s Cycle Detection Algorithm， 據說是由Robert W. Floyd所發明的演算法，所以以他的名字來命名，普遍上會以演算法的特色來稱呼：龜兔賽跑算法。顧名思義，這個演算法會假設一隻烏龜和 一隻兔子在這個許多節點構成的List結構進行賽跑，烏龜每次只能走一個節點，而兔子只能走二個節點，如果List結構存在著循環，他們只要跑下去肯定能到循環 裡，並且他們肯定能在循環中碰面或者在循環內的某一點會合(如下圖)。
然而，如果兔子走到結構中的終點卻沒跟烏龜會合的話，那就表示著結構不存著循環。(如下圖)
乍看之下這方法很簡單，但問題是這方法真能判別循環問題嗎？如果你對此也感到懷疑，歡迎到Proof章節來進行討論，但如果沒有的話，我可以告訴你 這方法確實能判別循環問題，而非是運氣，另外也建議讀者您參考Implementation以及Performance這兩個章節來看其代碼以及成本。
PROOF:HOW IT WORKS?
首先我們先來考慮擁有循環的結構(如下圖)，在循環之前可能會有N個點或者沒存在任何節點，而這N的值會影響著烏龜和兔子在循環中的初始位置，再來為了很好地瞭解影響，設定了數字來表示循環中的第幾個節點，以0到λ-1來命名，而λ則是定義成循環中的長度或者循環的總節點數，在這裡λ=10。
首先我們先考慮著N=0時，兔子和烏龜會在循環的起點會合，並從那裡開始進行他們的賽跑。
根據兔子走兩步和烏龜走一步的前提，當兔子走完一圈時，烏龜才走半圈，而兔子再走完下一個完整的圈時，這時烏龜才走完一圈，此時他們倆就在一開始的點會合。
在這裡，我們會發現幾個有趣的觀察結果：
- 兔子得走完一圈才有辦法跟烏龜會合(p.s 他們倆不動也能會合XD，但這不是在該方法的討論範圍內)
- 兔子H的步數會是烏龜T的步數之一倍，換言之，H=2T。
- 當兔子H和烏龜T都走到循環內部時，我們可以對H和烏龜T使用同餘(mod λ)的概念(如下式)來 確定是否存在循環，若兩者的餘數都一樣那就表示存在著循環；反之，就是不存在。
將第二個觀察結果納入至H ≡ T (mod λ)便會是如下式：
統整這三個觀察結果，我們會發現只要T=λ 代入上式，兔子和烏龜會在第0個節點會合。接下來我們思考另一種情況，如果N=1時，這種代入結果會不會有所不同？
從上圖可以觀察出當烏龜進入循環時的位置跟兔子所在的位置是不同的：兩者相差一個節點，這對於N=0所得出的觀察結果而言，我們可以確定兔子還是得走完一圈才 有辦法和烏龜在同一點，而第二、三個觀察結果可能會因為這樣而改變。
當烏龜進入循環的起點時，兔子在循環中的位置會變成(H′為循環中的新位置，H為循環中的舊位置)：
接著第三個觀察結果會因循環外的節點增加而改變成下式：
在兩者移動的過程中，仍然依照烏龜每走一步，兔子就會走兩步這前提，只是現在兔子比起原本多走了一步，所以我們可以將上式更改成：
你會發現這與N=0所發現的第二、三個觀察結果有些出入，在這裡第二個觀察結果會變成H′=2T+1，而第三個觀察結果就是上式。
那麼式子的改變會不會影響與烏龜會合的情況呢？其實只要我們按照圖上位置來模擬他們移動，最後會發現他們的確會在同一點會合，只是位 置變成第λ−1個位置，在這裡會是循環中編號9的位置，也就是說上式要達到同餘的效果就只有兩者都走到第九個位置(在這裡我們先假 定式子的同餘結果會是9，後續推理到N=M時來驗證)
接著我們再來思考一下N=2時，會有什麼樣的變化
同樣的，由於只是單純增加循環外面的節點，同樣地，由於位置因爲循環外的節點增加而改變第二、三個觀察結果，此時兔子的新位置會是：
而第二個觀察結果會變成是H′=2T+2，第三個觀察結果就變成是
接著我們只要按照圖上位置來模擬他們移動就會發現他們的確也是會在同一點上會合，但這次是第λ−2個節點或者第8個節點上會合， 如果考慮成N=3時，會發現會在第λ−3個節點或者第7個節點上會合，而N=4時，會發現在第λ−4個節點或者第6個節點 上會合。
那麼最後我們來試著考慮著N=M的情況，而M的數值範圍為[1,∞)
當烏龜進入循環時，兔子的預期位置變成：
在這裡我們還不確定這種情況是否同樣地使烏龜和兔子會在同一點會合，所以我們先假設他們肯定能在某一點會合來驗證其正確性。
我們考慮著以下式子：
同樣地，我們將烏龜走一步和兔子走兩步的前提納入進式子，就變成：
根據前面所述的第ㄧ、二觀察結果，兔子必須至少得繞ㄧ圈才有機會與烏龜會合，但這樣單純繞幾圈也只是與烏龜保持M(mod λ)−(λ−2M)(mod λ)個節點的差距，所以兔子和烏龜還必須在繞幾圈之後再多走個幾步才有機會會合，所以烏龜式子會變成如下：
接著將上式代入2T+M ≡ T (mod λ)就會是：
根據mod λ，我們可以化簡成：
根據先前N=2−4情況得到的觀察結果，會發現都會在第λ−N個節點會合，那麼同樣地將其結果套用在上式時，
會發現式子會變成如下:
再稍微用mod λ來化簡，則會是：
而這相當於在第λ−M個節點或者第λ−N個節點會合
從這樣推論驗證了N在[1,∞)範圍內的節點數所構成循環時可以使兔子和烏龜在第λ−N個節點會合，其中N=M。
其中λ−M中的λ其實原本是考慮成N′λ，但由於最後還是會因爲mod λ而跟λ−M的最後結果一樣，且如果寫N′λ−M的話，會不容易理解，在這裏簡化成最後解。此外，如果讀者願意花更多時間觀察的話，只要畫個圖並標示起點、會合點、距離的話(如下圖），會發現只要N與λ−N 相加就能構成循環長度，換言之，從起點1到會合點之間的節點數剛好是循環的長度。
另外剩下沒包含到的節點(用橘線來表示的節點)數量剛好會是循環外的節點數N
還有如果我們限制烏龜只能在循環內走不到一圈來和兔子會合，會得到一個有趣的觀察結果，其中烏龜走不到半圈時會使 兔子永遠會合不了，因此烏龜的步數要滿足走不到一圈以及會合的條件必須是半圈以上至一圈的範圍，所以，原本的式子 會改變成如下：
代入式子2T+M ≡ T會形成：
稍微處理一下，就能簡化成：
同時我們可以用先前得到的驗證結果來反證這樣子是否出現矛盾，首先右邊的式子在這前提下，必須等於−M或者λ−M ，那麼
將這個假設結果代入式子2M1+M≡λ2+M1就變成：
這樣子的結果等同於先前驗證結果，換言之，烏龜只需要繞半圈以上至一圈的距離就能和兔子會合。
先前我們假設烏龜和兔子會花好幾圈又幾個節點才能使他們會合，在這好幾圈又幾個節點的範圍內包含了無數個排列組合，比如2圈又5個節點，現在我們利用限制發現了其實烏龜走不到半圈就能會合。但這過程中，兔子還是得至少走一圈才能會合。基於這幾個推論結果，我們可以更改N=0的觀察結果：
- 兔子得走完一圈才有辦法跟烏龜會合(p.s 他們倆不動也能會合XD，但這不是在該方法的討論範圍內)。
- 考慮著循環內外節點數時，兔子H和烏龜T在循環內的位置關係會是H′=2T+N，而N是節點外的節點數。
- 當兔子H和烏龜T都從循環外部走到循環內部時，我們可以對H和烏龜T使用同餘(mod λ)的概念(如下式)來 確定是否存在循環，若兩者的餘數都一樣那就表示存在著循環；反之，就是不存在。(其中N為循環外的節點數)
4. 延伸第三個觀察結果，會發現兔子和烏龜的會合點會是第λ−N個節點或者第λ−M個節點。
5. 循環起點到會合點的節點數可以和循環外的節點數構成循環長度，換言之，λ=循環起點到會合點的距離+ 循環外的節點數。
6. 烏龜只需要繞半圈以上至一圈的距離就能和兔子會合。
第1個觀察結果因爲本身不受循環以外的節點數影響，所以不會進行變動，但原本第2−3個結果會隨之影響，使之擴展成考慮成M個循環以外的 節點，而第4−5個結果則是因爲第三個結果的推論過程而新增過來的。
PSEUDO CODE
根據Floyd’s Cycle Detection所描述的演算法而寫出的Pseudo Code，其中使用next[i]和head[i]來分別代表變數i的下一個節點以及 其頭部節點，而NIL在這裡代表不存在任何節點。
該演算法以List為輸入參數，當List輸入進去時，會先設定其頭部的位置給兔子和烏龜這兩個變數，接著為了他們兩個變數能夠在不影響系統的情況下 跑遍整個List結構，所以設定了While以及其條件為
Hare ≠ NIL and next[Hare]≠NIL
，其條件主要會檢測目前兔子所走的位置是否能繼續走， 最後兔子和烏龜會依照規則來走指定步數，當他們所在的位置是一樣時，就代表著此List結構確實存在循環而回傳True，反之兔子走到盡頭都沒遇到烏龜而 回傳代表不存在循環的False。
IMPLEMENTATION
程式碼連結：bit.ly/2FKotVP
使用EAFP程式碼風格來取代過度的if-else檢查，並從中提升速度，另外先讓在try區塊中的兔子多走一步以避免while迴圈判斷到錯誤的情況 ，同時這樣子的移動方式並不會改變兔子和烏龜的會合結果，只不過變成M+1個循環外節點的情況來移動。
PERFORMANCE
時間複雜度：考慮該方法應用在不存在循環以及存在循環的場景中，時間複雜度範圍會是O(N1+N2)-O(λ+N)，其中的N1 是循環外的起點1至循環內的起點2的節點數，而N2是循環內的起點2至烏龜與兔子預計會合點之間的節點數(如下圖)，而λ是 循環的長度以及N為循環外的節點數，N1、N2、λ和N這四個大小關係會因爲第六個觀察結果而會是λ+N≥N1+N2。
空間複雜度：該方法本身不需要向系統索求額外記憶體空間或者內存來進行判斷，所以空間複雜度會是原本一般執行程式碼所需要用到的記憶體 大小，也就是O(1)。
總結
我們利用一些場景來說明循環問題，接著將這些場景轉化成電腦可以判斷是否有循環的List結構，最後我們提出知名的龜兔賽跑算法來幫助電腦 判斷該List結構是否有循環。除此之外，我們也額外提供讀者一些章節來描述該方法是如何成功地判斷、如何實現以及其算法的執行成本。
