leecode 題解 || Merge k Sorted Lists 問題

problem：

Merge k sorted linked lists and return it as one sorted list.Analyze and describe its complexity.Tags Divide and Conquer Linked List Heap

合并K個已序單鏈表

thinking：

?（1）題目沒有要求不能夠新開ListNode,所以暴力破解法：提取K個list的keyword。排序、新建結點插入。這樣的情況對原list是否排好序沒有要求。

? ? ? ? ?排序時間復雜度能夠做到O(N* log N )。提取keyword和新建結點的時間復雜度都為O（N），所以總的時間復雜度為O（N*logN），這沒有考慮新建結點的時間浪費和空間 ? ? ? ? ? 浪費。

（2）採用能夠容納結點的容器，想到的是堆，或者堆的封裝-優先隊列，因為堆的O(N*logN)排序的時間復雜度。并且不用新開結點，節省空間。

暴力法：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *mergeKLists(vector<ListNode *> &lists) {ListNode *newlist=NULL;vector<int> tem;for(int i=0;i<lists.size();i++){while(lists.at(i)!=NULL){tem.push_back(lists.at(i)->val);lists.at(i)=lists.at(i)->next;}}if(tem.size()==0)return NULL;sort(tem.begin(),tem.end());for(int i=tem.size()-1;i>=0;i--){ListNode *p = new ListNode(tem.at(i));p->next = newlist;newlist = p;}return newlist;}//mergeKLists()};

優先隊列法：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class ListNodeCompare:public binary_function<ListNode*,ListNode*,bool>
{
public:bool operator()(ListNode* t1,ListNode* t2)const{if ( !t1||!t2 )return !t2;return t1->val>t2->val;}
};
class Solution {
public:ListNode *mergeKLists(vector<ListNode *> &lists) {// Note: The Solution object is instantiated only once and is reused by each test case.if (lists.empty())return NULL;priority_queue<ListNode*,vector<ListNode*>,ListNodeCompare> Q;for(int i=0;i<lists.size();i++)if ( lists[i]!=NULL)Q.push(lists[i]);ListNode guard(-1);ListNode* tail=&guard;while(!Q.empty()){ListNode* toAdd=Q.top();Q.pop();tail->next=toAdd;tail=tail->next;if (toAdd->next)Q.push(toAdd->next);}return guard.next;}
};