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

# 簡介 Intro

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

## 演算法解釋

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

![image.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1654650193749/flEbMJmpV.png align="left")

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

範例會用以下的圖作參考

![circularlinkedlist.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1654577570463/Y9__S0jPD.png align="left")

烏龜是 `t` 每次走一步、兔子是 `r` 每次走兩步。
0. `t` 和 `r` 從 3 開始出發
1. `t` 到 2、`r` 到 0
2. `t` 到 0、`r` 到 2
3. `t` 到 -4、`r` 到 -4 =>相遇了，所以判斷有迴圈存在

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

程式範例可以參考：[LeetCode Solution, Easy, 141. Linked List Cycle](https://blog.taiwolskit.com/leetcode-solution-easy-141-linked-list-cycle)

### 進階

進階的題目就像是 [LeetCode Solution, Medium, 142. Linked List Cycle II](https://blog.taiwolskit.com/leetcode-solution-medium-142-linked-list-cycle-ii) 是要找出迴圈的連接點。

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

```text
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` 可以看到 `l` 和 `f` 的長度就只差在迴圈長度的倍數，所以當今天常數 `n = 1`，就可以發現 `l = f` 了，因此當同時有兩個人分別從起點和相遇點開始走時，最後會在連接點相遇，由此找出連接點在哪。

## Reference

- [Floyd's Cycle Detection Algorithm (The Tortoise and the Hare)](https://web.archive.org/web/20160313063357/http://www.siafoo.net/algorithm/10)
- [Detect loop in linked list(floyd algo / Tortoise and hare algo)](https://youtu.be/zbozWoMgKW0)