題目網址：https://leetcode.cn/problems/merge-k-sorted-lists/

題意：給一 linked list array lists, 每個 linked list 都已按照升序排列。

將所有 linked list 合併成一個升序的 linked list, 並返回合併後的 linked list。

Solution 1：

想法：利用 Heap 來紀錄所有 linked list 當前的 node.val, 每次取 heap 中最小的 node cur, 並加到新的 linked list 中。若 cur->next 不為 null, 則將其加到 heap 中（能這樣做是因為每個 linked list 皆已排序過）

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        const auto cmp = [](auto& n1, auto& n2){
            return n1->val > n2->val;
        };

        // min heap
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> q(cmp);
        for (const auto& node : lists) {
            if (node) {
                q.emplace(node);
            }
        }

        ListNode *dummy = new ListNode(0), *tail = dummy;

        while (!q.empty()) {
            const auto top = q.top();
            q.pop();

            tail->next = top;
            tail = tail->next;

            if (tail->next) {
                q.emplace(tail->next);
            }
        }

        return dummy->next;
    }
};
  • time：$O(nk \cdot log(k))$
    • 假設每個 linked list 的平均長度為 n, 總共 k 個 linked list
    • $O(nk)$ : 總共有 $n \cdot k$ 個 node
    • $O(log(k))$ : heap 中的元素不超過 k 個, 因此每 insert / delete 一個 node 需花 $O(log(k))$
  • space：$O(k)$ ➔ heap 中的元素不超過 k

Solution 2：

想法：利用 merge sort, 類似 21. Merge Two Sorted Lists, 只是變成合併 k 個 list

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0) {
            return nullptr;
        }

        while (lists.size() > 1) {
            const int n = lists.size();
            vector<ListNode*> newLists;

            for (int i = 0; i < n; i += 2) {
                ListNode *l1 = lists[i];
                ListNode *l2 = (i + 1 < n) ? lists[i + 1] : nullptr;
                newLists.emplace_back(merge(l1, l2));
            }

            swap(lists, newLists);
        }

        return lists[0];
    }

private:
    ListNode* merge(ListNode *l1, ListNode *l2){
        ListNode *dummy = new ListNode(), *tail = dummy;

        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }

            tail = tail->next;
        }

        if (l1) {
            tail->next = l1;
        } else if (l2) {
            tail->next = l2;
        }

        return dummy->next;
    }
};
  • space：$O(nk \cdot log(k))$
    • 假設每個 linked list 的平均長度為 n, 總共 k 個 linked list
    • $O(log(k))$ : $\dfrac{k}{2^x} = 1$ ➔ $x = log(k)$ = 層數
    • $O(nk)$ : 共 $n \cdot k$ 個 node, worse case : 每個 node 皆被拜訪 $log(k)$ 次(每一層最多拜訪一次)
  • space：$O(n \cdot k)$ ➔ newLists