Algorithm 演算法 - 判圈系列 Floyd判圈算法(龜兔賽跑算法)

簡介 Intro 該算法據高德納稱由美國科學家羅伯特·弗洛伊德發明，但這一算法並沒有出現在羅伯特·弗洛伊德公開發表的著作。一個可以在有限狀態機、迭代函數或者鍊表上判斷是否存在環，求出該環的起點與長度的算法。 演算法解釋 下圖是這整個演算法的邏輯思維流程圖 演算法可以算是一種 Two-Pointer 的解法，可以想像在操場上跑步，在一個環當中，一個跑比較慢一個跑比較快，快的一定會追上慢的，以這個概念來判斷是否存在迴圈。 範例會用以下的圖作參考 烏龜是 t 每次走一步、兔子是 r 每次走兩步。 ...