LeetCode 142. Linked List Cycle II

Linked List Cycle II 是一道關於Linked List的經典算法題。給定一個Linked List，如果該Linked List中存在環，則返回環的起始節點。如果沒有環，則返回 null。

Python

方法一 :

利用 slow & fast pointer (slow 走一步，fast 走兩步)，如果遇到就是有 cycle。

如何找出 cycle node 呢?

假設 cycle 長度為 m:(1)假設 slow 走 K 步，代表 fast 走了 2K 步，此時相遇了，代表了 fast 比 slow 多繞了迴圈至少一次，因此 (2K – K) = n * m

(2) 此時一個人從起點開始走，另外一個人從相遇點開始走(一次都走一步)，會在 cycle node 相遇，為什麼?

原因:從起點走到相遇點是 K，而 K = n * m (迴圈的倍數)，因此這兩個人至少一定會在剛剛的相遇點相遇。而他們要能夠再相遇點相遇，則必定在 cycle node 就要遇到，才能夠一起走到相遇點!

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                temp = head
                while slow != temp :
                    slow = slow.next
                    temp  = temp .next
                return slow
        return None

方法二 :

首先，使用快慢指針確定鍊錶是否有環，如果沒有環則返回 null。
如果有環，找到快慢指針相遇的位置。
令一個指針從鍊錶頭部出發，另一個指針從相遇位置出發。
兩個指針同時移動，每次移動一個節點，當它們相遇時，相遇點即為環的起始節點

def detectCycle(head: ListNode) -> ListNode:
    # 第 1 步
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            # 第 2 步
            break
    
    if not fast or not fast.next:
        # 第 3 步
        return None
    
    # 第 4 步
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    return slow

C++

先使用快慢指針判斷鍊表是否有環。
如果有環，那麼我們需要找到環的起點。
我們設鍊錶頭節點到環起點的距離為 a，環起點到快慢指針第一次相遇點的距離為 b，快慢指針相遇點到環起點的距離為 c。根據快慢指針的速度關係可以得到：
快指針走過的距離 = 慢指針走過的距離 + n * 環長
快指針走過的距離 = 慢指針走過的距離 + 1 * 環長
經過計算可以得到：a = (n – 1) * 環長 + (環長 – c)，即鍊錶頭節點到環起點的距離等於 n – 1 圈的環長加上環長與環起點到相遇點的距離之和。
在快慢指針第一次相遇後，讓一個指針從鍊錶頭節點出發，另一個指針從相遇點出發，兩個指針都以相同的速度前進。它們將會在環起點處相遇。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) { // 相遇了
                ListNode *ptr = head;
                while (ptr != slow) { // 找環起點
                    ptr = ptr->next;
                    slow = slow->next;
                }
                return ptr;
            }
        }
        return nullptr; // 沒有環
    }
};

Python

C++

相關