# 23 - Merge k Sorted Lists

解法一 - K-way merge

這題主要就是要把 k 個 list 的 head 放到 min heap，然後就依序取出最小的 node，直到 min heap 是空的。

實作如下：

/**
 * 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) {
        // Corner case
        if(lists.empty()) return nullptr;

        // Put all head into min heap
        priority_queue<ListNode*, vector<ListNode*>, comp> minHeap;
        for(auto& l: lists) {
            if(l != nullptr) {
                minHeap.push(l);
            }
        }

        if(minHeap.empty()) {
            return nullptr;
        }

        // Keep taking the min node out and append to new head
        ListNode* dummyHead = new ListNode(-1);
        ListNode* ptr = dummyHead;
        while(!minHeap.empty()) {
            ListNode* cur = minHeap.top();
            minHeap.pop();

            ptr->next = cur;
            ptr = ptr->next;

            if(cur->next != nullptr) {
                minHeap.push(cur->next);
            }
        }

        ListNode* newHead = dummyHead->next;
        delete dummyHead;
        return newHead;
    }

private:
    struct comp {
        bool operator() (const ListNode* n1, const ListNode* n2) {
            return n1->val > n2->val;
        }  
    };
};