LeetCodeMergeKsortedLists

Merge k sorted
linked lists and return it as one sorted list. Analyze and describe its complexity.

采用最小堆，首先将 k 个首节点放入堆中，弹出最小的节点并插入到新的链表中；

                     弹出的节点如果next 非空，就将它的 下一个节点进 堆。 

                     继续，直到堆为空。

堆 Push 和 pop 的复杂度是 log(k), 所以复杂度是 nlg(k), n为总的节点数；

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *mergeKLists(vector &lists) {
int K = lists.size();
if (K == 0) return NULL;
else if (K == 1) return lists[0];

ListNode *listHead(NULL), *listRear(NULL);
ListNode *node(NULL);
priority_queue, cmp> h;

// push K list heads into heap
for(int i=0; i if(lists[i] != NULL){
h.push(lists[i]);
lists[i] = lists[i]->next;
}

while(!h.empty()){
//pop the min of k nodes
node = h.top(); h.pop();
if(node->next)
h.push(node->next);

//insert node into new list
if(listRear){
listRear->next = node;
listRear = listRear->next;
}
else{
listHead = listRear = node;
}
}

return listHead;
}
private:
struct cmp{
bool operator()(ListNode* lhs, ListNode *rhs){
if(lhs->val val) return false;
else return true;
}
};
};