【23】Merge k Sorted Lists

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

这里用到了优先队列，每次让权值最小的节点出队并让它的后一个节点（不为NULL）入队，直到队列为空。而如果当前只剩一条链不为空时，直接把这条链链接到最后。

struct cmp{ bool operator()(ListNode* a,ListNode* b){ return a->val > b->val; } }; ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<ListNode*,vector<ListNode*>,cmp> p_queue; ListNode* head=new ListNode(0); ListNode* p=head; int n=lists.size(); int rem=n; for(int i=0;i<n;i++){ if(lists[i])p_queue.push(lists[i]); else rem--; } while(!p_queue.empty()){ ListNode* temp=p_queue.top(); p_queue.pop(); p->next=temp; p=p->next; if(rem==1)break; if(temp->next)p_queue.push(temp->next); else rem--; } return head->next; }