Merge k Sorted Lists

问题描述：

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

知识补充：

删除vector中的元素

lists.erase(lists.begin()+i);//删除第i个位置的元素，注意此时vector动态改变，即此时i+1位置的元素变为现在的i位置 lists.erase(lists.begin()+i,lists.begin()+j);//删除区间[i,j)的元素

优先级队列

priority_queue<Type, Container, Functional> priQ;//Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。 priQ.push();//元素加入队列 priQ.top();//返回队列头部数据 priQ.pop();//队列头部数据出队 priQ.empty();//判断队列是否为空 priQ.size();//返回队列中数据的个数

测试代码：

ListNode* mergeKLists(vector<ListNode*>& lists) { int i=0,pos = 0; if(lists.empty()) return NULL; while(i<lists.size()) { if(!lists[i]) { lists.erase(lists.begin()+i); continue; } i++; } ListNode *p=lists[0]; ListNode dummy(INT_MIN); ListNode *tail = &dummy; while(!lists.empty()) { i = 0; p = lists[0]; pos = 0; while(i<lists.size()) { if(lists[i]->val<p->val) { p = lists[i]; pos = i; } i++; } tail->next = p; tail = tail->next; if(p->next) { p = p->next; lists[pos] = p; }else { lists.erase(lists.begin()+pos); } } return dummy.next; }

性能：

参考答案：

class Solution { public: // Need to use > because we want priority queue to return the min priority first struct priQueueCmp { bool operator() (const ListNode* l, const ListNode* r) { return l->val > r->val; } }; ListNode* mergeKLists(vector<ListNode*>& lists) { // Using priority queue to pick out min of the lists at each step. // Pri queue picks out the min in const time, but insertion and deletion takes // log time priority_queue<ListNode*, vector<ListNode*>, priQueueCmp> priQ; ListNode* head = NULL; ListNode* lastNode = NULL; // load up for(int i = 0; i < lists.size(); ++i) { if(lists[i] != NULL) priQ.push(lists[i]); } if(priQ.empty()) return head; head = priQ.top(); lastNode = head; priQ.pop(); if(head->next != NULL) priQ.push(head->next); while(!priQ.empty()) { ListNode* minNode = priQ.top(); lastNode->next = minNode; lastNode = minNode; priQ.pop(); if(minNode->next != NULL) priQ.push(minNode->next); } return head; } };

性能：