23.cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    static bool comp(ListNode *a, ListNode *b) {
        return a->val > b->val;
    }

    ListNode* mergeKLists(vector<ListNode*> &lists) {
        priority_queue<ListNode*, vector<ListNode*>, function<bool(ListNode*, ListNode*)>> min_heap(comp);
        int k = lists.size();
        for (int i = 0; i < k; ++i) {
            if (lists[i]) {
                min_heap.push(lists[i]);
            }
        }

        if (min_heap.empty()) {
            return NULL;
        }

        ListNode *curr = min_heap.top();
        min_heap.pop();

        ListNode *res = new ListNode(curr->val);
        ListNode *temp = res;

        if (curr->next) {
            min_heap.push(curr->next);
        }

        while (not min_heap.empty()) {
            curr = min_heap.top();
            min_heap.pop();
            if (curr->next) {
                min_heap.push(curr->next);
            }

            temp->next = new ListNode(curr->val);
            temp = temp->next;
        }

        return res;
    }
};