題目敘述
給定一個Linked list鏈結串列的Head node，
請判斷這條Linked list是否存在環路(Cycle)?
如果有環路，回傳True。如果沒有，回傳False。
測試範例
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
有環路Cycle
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
有環路Cycle
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
沒有環路
約束條件
Constraints:
- The number of the nodes in the list is in the range
[0, 10^4].
Linked list的節點總數目介於 0 ~ 一萬之間。
-10^5 <= Node.val <= 10^5
每個節點的節點值都介於 負十萬~正十萬 之間。
posis-1or a valid index in the linked-list.
pos代表發生環路的節點編號，如果是-1代表沒有環路。
進階提問
Follow up: Can you solve it using O(1) (i.e. constant) memory?
能不能在常數空間複雜度的條件下，解出這題?
演算法 雙指針(快/慢 指針) 俗稱龜兔賽跑演算法
有一個比較直覺的想法，就是沿路記下每個節點的ID，在C/C++裡面可以記錄節點的記憶體位置，在python裡面可以記錄run-time的物件ID。如果在拜訪的過程中，遇到相同的ID，就代表有環路。
但是，這個方法會耗費O(n)的空間成本去紀錄節點的ID，有沒有更好的方法呢?
其實有喔!
(俗稱龜兔賽跑演算法，或者Floyd cycle detection algorithm)
想一下，假如有環路發生，我們可以說linked list中的某一塊形成了封閉的環型，就好像操場跑道的形狀。
我們讓兩個跑者(在演算法裡面就是雙指針，快/慢指針)，同時從起點出發，快的固定都跑得比慢的還快，最後快的一定可以領先一圈，又遇到慢的跑者。
相反的，如果沒有環路，相當於linked list是一條直線型的跑道，那麼我們讓兩個跑者同時從起點出發，兩者並不會在中途相遇。
為了方便實作，我們可以假設快跑者是慢跑者的兩倍速度，讓他們同時從起點出發。
假如快、慢跑者中途會相遇，那麼代表linked list 存在至少一個環路。
假如快、慢跑者不會相遇，那麼代表linked list是一條直線的串列，沒有環路。
這樣我們只要維護兩個pointer 快、慢指針就相當於快、慢跑者，
只需要常數空間O(1)即可。
程式碼 雙指針(快/慢 指針) 俗稱龜兔賽跑演算法
class Solution:
def hasCycle(self, head: ListNode) -> bool:
# two pointers
slow, fast = head, head
# slow runner move 1 step, fast runner move 2 steps per iteration
# if fast runner meets slow one somewhere, then there is a cycle in linked list
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
return True
return False
複雜度分析
時間複雜度:
需要掃描過每個節點，所需時間為O(n)。
空間複雜度:
只需要維護固定尺寸的臨時變數，所需空間為O(1) 常數級別。
關鍵知識點
假如有環路發生，我們可以說linked list中的某一塊形成了封閉的環型，就好像操場跑道的形狀。
我們讓兩個跑者(在演算法裡面就是雙指針，快/慢指針)，同時從起點出發，快的固定都跑得比慢的還快，最後快的一定可以領先一圈，又遇到慢的跑者。
相反的，如果沒有環路，相當於linked list是一條直線型的跑道，那麼我們讓兩個跑者同時從起點出發，兩者並不會在中途相遇。
Reference:
