runtime 16 ms, beats 99.38% of cpp submissions
O(nlog(k)) solution with explanation

tags: linked list, heap, divide and conquer

Merge k Sorted Lists

📖 description

給定 k 個 sorted list ，將他們 merge 成一個 sorted list 。

🧠 solution

最簡單的想法是從頭到尾兩兩 merge 起來，但這樣做的話永遠有一邊較長的 (很多 list 合成的結果)，所以必須想辦法每次 merge 的時候都是挑到最短的兩個 list ，這樣做的計算消耗是比較低的。

heap (by length)

於是便可以使用 priority queue 來達成，我們可以以 list 的長度作為比較的依據，並維護一個 min heap ，讓每次 merge 都從小的開始。

ex.
    [
      1.  2->6     (長度 2 )
      2.  1->3->4  (長度 3 )
      3.  1->4->5  (長度 3 )
    ]

    先 merge 1、2

    [
      1.  1->4->5        (長度 3 )
      2.  1->2->3->4->6  (長度 5 )
    ]

    再 merge 1、2

    [
      1. 1->1->2->3->4->4->5->6  (長度 8 )
    ]

divide and conquer

(此方法的時間消耗比較少，且空間複雜度也比較低)
為了達到每次都挑最短 list 的目的，需要在一開始時遍歷所有的 list 來獲得長度，但也可以單純不要一直用到 merge 完的結果，使用 merge sort 的概念，針對每一層向下 merge 出第二層，雖然沒辦法確保每次挑到的都是最好的，但可以用多遍歷一次所有的 list 。

    list0   list1   list2   list3   list4   list5
        \   /           \   /           \   /
        list0           list2           list4
            \           /                 |
                list0                   list4
                    \                   /
                            list0

⏳ time complexity

n 表示所有 list 總和的長度， k 表示有幾個 list ，在 priority queue 內共有 log(k) 次操作
總時間複雜度 O(nlog(k))

📝 code

heap (by length)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
struct list_obj{
    ListNode* lis;
    int len;
    bool operator<(const list_obj& a) const {  // 把長度小的擺到前面
        return len>a.len;
    }
};
class Solution {
public:
    int get_len(ListNode* head){    // 獲得長度
        auto tmp = head;
        int cnt = 0;
        while(tmp!=nullptr){
            tmp = tmp->next;
            cnt++;
        }
        return cnt;
    }
    ListNode* merge(ListNode* a, ListNode* b){   // merge 兩個 list
        auto head = new ListNode();
        auto tmp = head;
        ListNode* node;
        while(a!=nullptr && b!=nullptr){
            if(a->val<b->val){
                node = a;
                a = a->next;
            }
            else{
                node = b;
                b = b->next;
            }
            tmp->next = node;
            tmp = tmp->next;
        }
        if(a!=nullptr){
            tmp->next = a;
        }
        if(b!=nullptr){
            tmp->next = b;
        }
        return head->next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size()==0){
            return nullptr;
        }
        priority_queue<list_obj> pq;
        for(int i=0;i<lists.size();i++){
            pq.push(list_obj{lists[i],get_len(lists[i])});
        }
        while(pq.size()>=2){
            auto a = pq.top();
            pq.pop();
            auto b = pq.top();
            pq.pop();
            pq.push(list_obj{merge(a.lis,b.lis),a.len+b.len});  //拿出兩個最短的 list merge
        }
        return pq.top().lis;
    }
};

divide and conquer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    ListNode* merge(ListNode* a, ListNode* b){      // merge 兩個 list
        if(a==nullptr){
            return b;
        }
        else if(b==nullptr){
            return a;
        }
        ListNode* head;
        if(a->val<=b->val){
            head=a;
            a=a->next;
        }
        else{
            head=b;
            b=b->next;
        }
        auto tmp = head;
        ListNode* node;
        while(a!=nullptr && b!=nullptr){
            if(a->val<b->val){
                node = a;
                a = a->next;
            }
            else{
                node = b;
                b = b->next;
            }
            tmp->next = node;
            tmp = tmp->next;
        }
        if(a!=nullptr){
            tmp->next = a;
        }
        if(b!=nullptr){
            tmp->next = b;
        }
        return head;
    }
    ListNode* merge_all(vector<ListNode*>& lists,int l,int r){      // merge sort 的概念
        if(l>=r){
            return lists[l];
        }
        int mid = (r+l)/2;
        ListNode* left = merge_all(lists,l,mid);        // 針對左半邊
        ListNode* right = merge_all(lists,mid+1,r);     // 針對右半邊 
        return merge(left,right);                       // merge 左右
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size()==0){
            return nullptr;
        }
        return merge_all(lists,0,lists.size()-1);
    }
};