Merge _k _sorted linked lists and return it as one sorted list.

Analyze and describe its complexity.

[

2->4->null,

null,

-1->null

],

return -1->2->4->null.

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    struct compare{
        bool operator()(const ListNode* n1, const ListNode* n2) {
            return n1->val > n2->val;
        }
    };

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // write your code here
        int size = lists.size();
        if (size == 0) {
            return NULL;
        }

        if (size == 1) {
            return lists[0];
        }

        priority_queue<ListNode*, vector<ListNode*>, compare > pQ;

        for (int i = 0; i < size; i++) {
            if (lists[i] != NULL) {
                pQ.push(lists[i]);
            }
        }

        ListNode* dummy = new ListNode(0);
        ListNode* tail = dummy;

        while (!pQ.empty()) {
            ListNode* head = pQ.top();
            pQ.pop();
            tail->next = head;
            tail = head;
            if (head->next != NULL) {
                pQ.push(head->next);
            }
        }

        return dummy->next;
    }
};