今天要來解的題目是 Leetcode－141. Linked List Cycle，難度為易，
而我所使用的語言是 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.
Return true if there is a cycle in the linked list. Otherwise, return false.
題目只會給你 head (起始點的節點)，
你並不會知道一共有幾個 node，並且只能用 node.next 去下一個節點。
我們的目標是要找出是否有 cycle。
貳、開始解題
先用最簡單的方法來思考這個問題，
今天一一走過並且記錄下所有走過的 node，
如果你走一走發現，疑！這個 node 我已經走過了，
那這時候就要回傳 True，表示 cycle 存在。
直接給 code！
下方的程式碼中，seen 這個 set 就是在做紀錄，
這樣的複雜度呢？
【空間】seen 最多可能塞入多少個元素呢？
最糟的情況，一直走到盡頭了、完全沒有 cycle，那 seen 會塞入所有經過的 node = O(n)
【時間】
最糟的情況同樣是完全沒有 cycle，那麼 while loop 就會跑完整個 list。
結果：Accepted！
參、有更好的做法嗎？
有的！有個解法可以維持時間複雜度 O(n)，但空間複雜度卻降到 O(1)
但沒碰過還真想不到，Floyd's Tortoise and Hare (Cycle Detection)
今天我們讓龜 & 兔從起點開始跑步，
（兔子跑比較快，每次跳兩格；烏龜比較慢，每次走一格）
如果該 list 有 cycle，那兔子總有一天會倒追上烏龜；
但如果該 list 沒有 cycle（直線跑道之類的），那兔子抵達終點、直接結束。
所以我們要回答的是以下問題：「起跑以後，兔子會不會和烏龜再一次相遇？」
程式碼來！
結果：Accepted！
不僅速度變快了，空間複雜度也減少了，大家有發現嗎～
留言列表
