Sofie 舒霏的部落格

今天要來解的題目是 Leetcode－142. Linked List Cycle II ，難度為中等，

而我所使用的語言是 python3

壹、理解題目

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Notice that you should not modify the linked list.

簡單而言，就是

如果有 cycle：回傳 cycle 的起始點

如果沒有：回傳 None

其實這題是 141 的延伸題（如何判斷有沒有 cycle？）

在做這題之前，可以先點進這裡看 141 的解法喔！

同樣會使用到此演算法：Floyd's Tortoise and Hare (Cycle Detection)

貳、開始解題

解決 141 後，你應該就知道如何判斷是否有 cycle 了！

就是龜兔第二次相遇的時候，但

他們第二次相遇的 node 不一定會是 cycle 的起始點 (cycle head)，

那麼 要如何找到 cycle head 呢？

在結束第一階段－讓兩者相遇之後，

讓 tortoise 回到原點，而 hare 每次只走一步 (just like tortoise)，

直到兩者再次相遇，那個點就會是 cycle head！

Why？

所有的 case 都可以簡化成以下的圖

L 是起始點和 cycle head 的距離、x 是 cycle head 到第一次見面的距離、C 是整個 cycle 的長度

其中，L, x 都可以是 0

（L = 0 代表一開始就在 cycle；x = 0 代表剛剛好第一次遇到就是在 cycle head）

第一次相遇可以寫一個等式：2(L+x) = L+nC+x

(L+x) 代表 tortoise 走的步數，(L+nC+x) 是 hare 走的步數，

為何 hare 多 + 了 nC，因為我們不能確定 hare 在等到 tortoise 來之前，繞了幾次 cycle 了。

又，該等式可以簡化成 L+x = nC

接著，要證明一定會在 cycle head 相遇：

讓 tortoise 回到起點 (0)，走 L 步到 cycle head (L) 的同時，

hare 從第一次相遇的地方 (L+x)，走了一樣的步數 L 會到哪？

(L+x)+L 代入上面得到的 = nC+L 阿不就是 L 的位子, i.e. cycle head 嗎！

觀念都了解以後，就可以看程式碼了～