攻城獅
Not a programmer 不工程的攻城獅

Follow

Not a programmer 不工程的攻城獅

Follow

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

Floyd Cycle Detection Algorithm(Tortoise and Hare Algorithm)

攻城獅's photo
攻城獅
·Jun 8, 2022·
Play this article

簡介 Intro

該算法據高德納稱由美國科學家羅伯特·弗洛伊德發明,但這一算法並沒有出現在羅伯特·弗洛伊德公開發表的著作。一個可以在有限狀態機、迭代函數或者鍊表上判斷是否存在環,求出該環的起點與長度的算法。

演算法解釋

下圖是這整個演算法的邏輯思維流程圖

image.png

演算法可以算是一種 Two-Pointer 的解法,可以想像在操場上跑步,在一個環當中,一個跑比較慢一個跑比較快,快的一定會追上慢的,以這個概念來判斷是否存在迴圈。

範例會用以下的圖作參考

circularlinkedlist.png

烏龜是 t 每次走一步、兔子是 r 每次走兩步。

  1. tr 從 3 開始出發
  2. t 到 2、r 到 0
  3. t 到 0、r 到 2
  4. t 到 -4、r 到 -4 =>相遇了,所以判斷有迴圈存在

而如果不存在迴圈的話,r 會先走到結尾沒有下一個節點,所以當 r = null 的時候就知道迴圈不存在了。因為使用 Two-Pointer 的方式所以空間複雜度就只需要常數而已,而時間複雜度只有 O(n)n 是節點數

程式範例可以參考:LeetCode Solution, Easy, 141. Linked List Cycle

進階

進階的題目就像是 LeetCode Solution, Medium, 142. Linked List Cycle II 是要找出迴圈的連接點。

延續上面的範例,c 是迴圈的長度、l 是起點到迴圈連接點的長度、x 是連接點到第一次相遇點的長度。 從第一次相遇點的位置到連接點 f = c - x

r = l + x + n * c // c 會乘上 n 是因為在遇到 t 之前不確定已經先走了幾圈
t = l + x

l + x + n * c = 2 * (l + x)  // r 每次走兩步, t 只走一步,所以總長上 r 會走 t 的兩倍
l + x + n * c = 2 * l + 2 * x
n * c = l + x      // 簡化的結果,從起始點到相遇點是迴圈的倍數 

l + x = (n - 1) * c + c
l + x = (n - 1) * c + f + x
l = (n - 1) * c + f

最後的結果 l = (n - 1) * c + f 可以看到 lf 的長度就只差在迴圈長度的倍數,所以當今天常數 n = 1,就可以發現 l = f 了,因此當同時有兩個人分別從起點和相遇點開始走時,最後會在連接點相遇,由此找出連接點在哪。

Reference

Did you find this article valuable?

Support 攻城獅 by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this