Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list.

Analyze and describe its complexity.

Have you met this question in a real interview? 

Yes

Example

Given lists:

[
  2->4->null,
  null,
  -1->null
],

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

如果是两个list 合并的话，比较一下大小，o(m+n)的时间复杂度， 但是如果合并k个数组的话，需要排序，实际上就变成了klgk *(m+n)了。。。如果借用heap的话，复杂度可以降到lgk(m+n)。。。

/**
 * 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()(ListNode* left, ListNode* right){
            return left->val>right->val;
        };
    };
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // write your code here
        priority_queue<ListNode*, vector<ListNode*>, compare> queue;
        ListNode dummy(0);
        ListNode* head=&dummy;
        for (int i=0; i<lists.size();i++){
            if (lists[i])
                queue.push(lists[i]);
        }
        while(!queue.empty()){
            ListNode* tmp=queue.top();
            queue.pop();
            if (tmp->next)
                queue.push(tmp->next);
            head->next=tmp;
            head=head->next;
        }
        if(head)
            head->next=0;
        return dummy.next;
    }
};