23. Merge k Sorted Lists

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    static bool cmp(ListNode* a, ListNode *b) {
        return a->val > b->val;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *head = NULL, **curr = &head;
            //= NULL!!
        vector<ListNode*> minHeap;

        for (int i = 0; i < lists.size(); i++)
            if (lists[i]) minHeap.push_back(lists[i]);
            //pay attention: without "if (lists[i])", in the case of [[]], it will die;
        make_heap(minHeap.begin(), minHeap.end(), cmp);

        while(minHeap.size()) {
            *curr = minHeap.front();
            pop_heap(minHeap.begin(), minHeap.end(), cmp);
            minHeap.pop_back();
            if ((*curr)->next != NULL) {
                minHeap.push_back((*curr)->next);
                push_heap(minHeap.begin(), minHeap.end(), cmp);
            }
            curr = &((*curr)->next);
        }

        return head;
    }
};