[LeetCode] 23. Merge k Sorted Lists

23. Merge k Sorted Lists

• Hardness: \(\color{red}\textsf{Hard}\)
• Ralated Topics: Linked List、Divide and Conquer、Heap (Priority Queue)、Merge Sort

一、題目

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

• Input: lists = [[1,4,5],[1,3,4],[2,6]]
• Output: [1,1,2,3,4,4,5,6]
• Explanation: The linked-lists are:
  [
  1->4->5,
  1->3->4,
  2->6
  ]
  merging them into one sorted list:
  1->1->2->3->4->4->5->6

Example 2:

• Input: lists = []
• Output: []

Example 3:

• Input: lists = [[]]
• Output: []

Constraints:

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 10^4.

二、分析

• 由於所有鏈表都是排序好的，故我們可以同時比較所有鏈表 head 的值，來依序把鏈表建起來。
• 這裡可以用到 priority_queue，以下是 custom comparator 的寫法：

  auto comp = [](const auto& a, const auto& b) { return condition; } ;
  1. priority_queue<element, container, decltype(comp)> pq(iterator::start, iterator::end, comp);
  2. priority_queue<element, container, decltype(comp)> pq(comp);
  

• 需要特別 [] 與 [[]] 的差異，都可以藉由加入 heap 時先檢查鏈表來避免，
  • 注意! 直接用 priority_queue 的 initializer 去加入整個 vector 會把 null 加進優先佇列中而導致報錯。

三、解題

1. Heap (Priority Queue)

• Time complexity: \(O(k\times n\log k)\)
• Space complexity: \(O(k\times n)\)

ListNode* mergeKLists(vector<ListNode*>& lists) {
    auto comp = [](const auto& a, const auto& b) {return a->val > b->val;};     // min heap 的寫法跟 sort 相反
    priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> pq(comp);
    ListNode* dummy = new ListNode(-1);     // 建立 dummy head
    ListNode* curr = dummy;
    for (const auto& list : lists) {
        if (list) pq.push(list);            // 排除空鏈表
    }
    while (!pq.empty()) {
        curr->next = pq.top();
        pq.pop();
        if (curr->next->next) pq.push(curr->next->next);    // 若鏈表還有 next，繼續加入 min heap
        curr = curr->next;
    }
    
    return dummy->next;
}

回目錄 Catalog