快慢指針題型

題目連結: 142. Linked List Cycle II

題目描述:給你一個鏈結串列的頭節點 head。如果這個鏈結串列存在一個環，你需要返回那個環開始的節點。如果沒有環，就返回 null。

Input: head = [3,2,0,-4], pos = 1

Output: tail connects to node index 1

Explanation: There is a cycle in the linked list, where tail connects to the second node.

Input: head = [1,2], pos = 0

Output: tail connects to node index 0

Explanation: There is a cycle in the linked list, where tail connects to the first node.

Python

解題思路:

• 當 slow 和 fast 在環內相遇後，如果我們再派一個全新的指針 pre 從 head 出發，同時讓原來的 slow 指針也從「相遇點」出發，兩個指針都以相同的速度前進，那麼它們下一次相遇的地方，就正好是環的入口。

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

        return None

演算法分析:

• 初始化 slow = head, fast = head。
• 如果沒有環，返回 None。
• 如果有環，則在 slow 和 fast 相遇後，pre 和 slow（都是指向下個值），直到它們再次相遇。
• 相遇點就是環的入口，return pre。

複雜度分析:

• 在最壞的情況下，指針需要遍歷幾乎整個鏈結串列才能相遇。這個過程的時間複雜度為 O(n)。

• 尋找環入口的迴圈次數是根據 頭部到環入口的距離，過程的時間複雜度是 O(x)，而 x 不會超過 n，所以也是 O(n)。

• 整體的時間複雜度是 O(n) + O(n)，簡化後為 O(n)。

• 空間複雜度： O(1)(只宣告了 fast、 slow、 pre)。

有問題可以底下留言!
下回見!!