# 23 - Merge k Sorted Lists

解法一 - 暴力法之全部丟到 vector 排序

這一題用暴力想起來有幾種做法:

1. 每次都比較所有 list 的 head，慢慢建構出新的 list

2. 一次 merge 兩個 list，直到 merge 完所有 list

3. 把所有 list 的 val 都塞到一個 vector 中，對 vector 中的元素排序完，再重新建立新的 list

想起來覺得 3 比較簡單，先實作看看：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return NULL;

        // Store all values to a vector
        vector<int> nodeVal;

        for( auto &head : lists) {
            ListNode* ptr = head;

            while(ptr) {
                nodeVal.push_back(ptr->val);
                ptr = ptr->next;
            }
        }

        if(nodeVal.empty()) return NULL;

        // Sort the vector
        sort(nodeVal.begin(), nodeVal.end());

        // Create the new list
        ListNode* newHead = new ListNode(nodeVal[0]);
        ListNode* ptr = newHead;

        for(int i=1; i<nodeVal.size(); i++) {
            ptr->next = new ListNode(nodeVal[i]);
            ptr = ptr->next;
        }
        ptr->next = NULL;

        return newHead;
    }
};

上面這樣做的時間複雜度會是 O(NlogN)（把所有 node 存到 vector 是 O(N)，sort 是 O(NlogN)，建立新的 list 是 O(N)），其中 N 是所有 node 的總數。空間複雜度是 O(N)。

這樣做的速度其實不算太慢，只是會用到比較多記憶體：

Runtime: 20 ms, faster than 99.65% of C++ online submissions for Merge k Sorted Lists. Memory Usage: 12 MB, less than 28.13% of C++ online submissions for Merge k Sorted Lists.

解法二 - 每次都比較 k 個 list

為求通達，接著讓我們來實作另一種暴力法，程式碼如下：

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return NULL;

        // Compare all heads' values and insert to new list
        ListNode *dummy = new ListNode(0);
        ListNode *ptr = dummy;

        // There is k lists, so we should use a flag to break while loop
        bool keepSort = true;
        while(keepSort) {
            keepSort = false;

            int minIdx = -1;
            int min = INT_MAX;

            for(int i=0; i<lists.size(); i++) {
                if(lists[i]) {
                    if(lists[i]->val < min) {
                        min = lists[i]->val;
                        minIdx = i;
                    }

                    keepSort = true;
                }
            }

            if(minIdx >= 0)
            {
                ptr->next = new ListNode(min);
                ptr = ptr->next;
                lists[minIdx] = lists[minIdx]->next;
            }
        }

        // Return result and clean garbage
        ListNode* newHead = dummy->next;
        delete dummy;
        return newHead;
    }
};

時間複雜度乍想之下會覺得有點難，不過如果我們用最粗的方向來想，可以發現若每個 list 都足夠長，而且值散佈得很平均，那每選出一個 node 大概都要比 k 次，所以時間複雜度是 O(kN)。

img

這個方法果然有夠慢，實際跑起來的結果是：

Runtime: 392 ms, faster than 11.00% of C++ online submissions for Merge k Sorted Lists. Memory Usage: 11.5 MB, less than 56.48% of C++ online submissions for Merge k Sorted Lists.

解法三 - 一次 merge 兩個 list，直到 merge 完

i

解法四 - 用 priority queue 不斷排序

事實上這個解法比較像是解法一的優化版本，因為解法一是等到所有東西都被塞到 vector 之後才一次排序，所以時間複雜度是 O(NlogN)。而如果是用 priority queue，因為可以用 priority queue 在 pop 的時候再不斷比較 k 個 list，所以時間複雜度變成 O(Nlogk)!

做法可以先參考下面的 python code：

from Queue import PriorityQueue

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        head = point = ListNode(0)
        q = PriorityQueue()
        for l in lists:
            if l:
                q.put((l.val, l))

        // pop()完，重新 put 時再比較大小
        while not q.empty():
            val, node = q.get()
            point.next = ListNode(val)
            point = point.next
            node = node.next
            if node:
                q.put((node.val, node))
        return head.next

i

解法五 - Divide and Conquer

Reference

• Leetcode solution