LeetCode 23. Merge k Sorted Lists [Hard] [C++] 解題筆記

這題給定 k 個排序好的 linked list，要求將這 k 個 list 合併成一個排序好的 linked list。

EX:

        Input:

    [
      1->4->5,
      1->3->4,
      2->6
    ]
    Output: 1->1->2->3->4->4->5->6

想法:

    這題主要有兩種作法，第一種可以利用 priority queue，首先把所有 list 的 head 都放進 pq 中，之後就

可以利用 pq 的特性取得目前最小的 head ，之後再將 head->next 放進 pq 中，依此類推直到 pq 為空。

第二種方法就是利用 merge sort 的概念，我們可以將這 k 個 list 想像成 k 段已經排序好的區間，因此我們只要

利用類似 merge sort 的 divide and conquer 技巧將區間以 bottom up 的方式兩兩合併即可得到排序好的 list，

這邊 list 兩兩合併可以直接利用 LeetCode 21. Merge Two Sorted Lists 來進行合併。

Complexity: O(nklogn) time, O(logn) / O(n) space

where n is number of list and k is max length of each list.

O(n) space in priority_queue method, since at most n nodes in the queue at same time.

完整程式碼:

解法一(priority_queue):

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode dummy(0);
        ListNode *tail = &dummy;
        auto cmp = [](const ListNode *n1, const ListNode *n2) -> bool{
            return n1->val > n2->val;
        };
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
        
        for (auto list : lists) {
            if (list) {
                pq.push(list);
            }
        }
        
        while (!pq.empty()) {
            tail->next = pq.top();
            pq.pop();
            tail = tail->next;
            if (tail->next) { 
                pq.push(tail->next); 
            }
        }
        
        return dummy.next;
    }
};

解法二(divide and conquer):

class Solution {
public:
    ListNode* mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode dummy(0);
        ListNode *cur = &dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            }
            else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        cur->next = (l1)? l1 : l2;
        
        return dummy.next;
    }
    
    ListNode* merge(vector<ListNode*>& lists, int l, int r) {
        if (l > r) { return nullptr; }
        if (l == r) { return lists[l]; }
        // just two lists
        if (l + 1 == r) { return mergeTwoLists(lists[l], lists[r]); }
        int m = (l + r) / 2;
        auto l_head = merge(lists, l, m);
        auto r_head = merge(lists, m + 1, r);
        return mergeTwoLists(l_head, r_head);
    }
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};