0%
Loading ...

【Leetcode 筆記】23. Merge k Sorted Lists

題目解釋

給定一個由 k 個 linked list 組成的 array,每個 linked list 都是 ascending sorted 的。

將所有 linked list 合併為一個已排序的 linked list 並 return。

範例

  • 輸入: lists = [[1, 4, 5],[1, 3, 4],[2, 6]]
  • 輸出: [1, 1, 2, 3, 4, 4, 5, 6]

lists 中的所有 linked lists 都被整合到同一條 linked list 了。

最佳解法

我們可以把這題拆解為

  1. Merge 兩條 linked list
  2. 逐步將 lists 中的所有 linked list 合併
  3. 直到最後 lists 中只剩下一條 linked list 時,return

說明

為了使用方便,
我們將 Merge 兩條 linked list 的邏輯 func 命名為 _merge_two_lists
這是承襲自 【Leetcode 筆記】21. Merge Two Sorted Lists
有興趣的讀者可以再回去複習。

分而治之法 (Divide and Conquer)

那關於合併的部分,我們必須用滾動的方式逐一將 linked list 們合併。

我們不斷向前滾動,traverse 整條 lists
並 merge lists[i]lists[i + 1]

要注意的是取 lists[i + 1] 的時候要看有沒有越界,
如果越界的話就要把 lists[i + 1] 設成 None

當上面的滾完一次後其實還遠遠沒有結束,
因為我們只是先兩步兩步的將 lists 中的元素合併,舉個例子:

[[1], [2], [3], [4], [5]]
=> [[1, 2], [3, 4], [5]] (第一次 iteration)
=> [[1, 2, 3, 4], [5]] (第二次 iteration)
=> [[1, 2, 3, 4, 5]] (第三次 iteration)

在第三次 iteration 時,我們應該停止。

因此最後我們的 boundry condition 就是,
lists 中只剩下一條 linked list 時我們才停止,並回傳 lists[0]

這邊隱含的概念就是 分而治之法 (Divide and Conquer)

        # Edge case handling
        if not lists:
            return None
        if len(lists) == 1:
            return lists[0]

        # Divide and Conquer !
        while len(lists) > 1:
            merged_lists = []

            for i in range(0, len(lists), 2):
                list1 = lists[i]

                if i + 1 < len(lists):
                    list2 = lists[i + 1]
                else:
                    list2 = None
                merged_lists.append(_merge_two_lists(list1, list2))

            # Update current `lists` status
            lists = merged_lists

        return lists[0]

完整程式碼在下方。

程式碼

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        def _merge_two_lists(list1, list2):
            new_head = ListNode()
            curr = new_head

            while list1 and list2:
                if list1.val <= list2.val:
                    curr.next = list1
                    list1 = list1.next
                else:
                    curr.next = list2
                    list2 = list2.next
                curr = curr.next

            if list1:
                curr.next = list1
            if list2:
                curr.next = list2

            return new_head.next

        if not lists:
            return None
        if len(lists) == 1:
            return lists[0]

        while len(lists) > 1:
            merged_lists = []

            for i in range(0, len(lists), 2):
                list1 = lists[i]

                if i + 1 < len(lists):
                    list2 = lists[i + 1]
                else:
                    list2 = None
                merged_lists.append(_merge_two_lists(list1, list2))

            lists = merged_lists

        return lists[0]

時間複雜度

O(n log k),n 是 lists 的元素個數,k 是 linked list 的數量。

空間複雜度

O(1),如果不考慮 linked list 節點本身佔用的空間。
該演算法的空間複雜度主要是由合併時新生成的 head 節點以及每次合併後的 merged_lists 佔用的空間,這部分是常數級別的。

結語

類似於 Merge Sort 的 linked list 題目。

數據女巫 𝔻.𝕡𝕪𝕤 🔮

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

The reCAPTCHA verification period has expired. Please reload the page.