用 龜兔賽跑演算法 來檢查有沒有環路Linked List Cycle_Leetcode #141

Janan Lagerwall on Unsplash

題目敘述

給定一個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

每個節點的節點值都介於 負十萬~正十萬 之間。

• pos is -1 or 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中的某一塊形成了封閉的環型，就好像操場跑道的形狀。

我們讓兩個跑者(在演算法裡面就是雙指針，快/慢指針)，同時從起點出發，快的固定都跑得比慢的還快，最後快的一定可以領先一圈，又遇到慢的跑者。

Zetong Li on Unsplash

相反的，如果沒有環路，相當於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:

[1] Linked List Cycle - LeetCode