本文共 5541 字，大约阅读时间需要 18 分钟。
题目：
五种方法
/*------------------------------------------------------------------*/class Solution1 {public: ListNode* mergeKLists(vector & lists) { //两个两个比较，直到最后合成一个(这个方法超时，AC不了)复杂度O(N*K^2) ListNode* result=NULL; if(lists.size()==0) return result; else if(lists.size()==1) return lists[0]; else { for(int i=0;i =2) { result=merge2Lists(lists[i],result); } } return result; } }private: ListNode *merge2Lists(ListNode*l1,ListNode*l2 ) { if(l1==NULL) return l2; else if(l2==NULL) return l1; else { ListNode *res=NULL; if(l1->val val) { res=l1; res->next=merge2Lists(l1->next,l2); } else { res=l2; res->next=merge2Lists(l1,l2->next); } return res; } }}; 2.
分治法（两个两个合并，第一次合并结束，是k/2个序列，再两个两个合并，第二次合并结束是 k/4，最后的复杂度是O(N*log(K))）
/*------------------------------------------------------------------*/class Solution2 { //复杂度：O(N*log(K)) 空间复杂度大public: ListNode* mergeKLists(vector & lists) { //分治法，一半一半比较，直到最后合成一个(这个方法AC了，不会存在空间超出限制,70%排名) ListNode* result=NULL; if(lists.size()==0) return result; else if(lists.size()==1) return lists[0]; return merg(lists,0,lists.size()-1); }private: ListNode *merg(vector & lists,int left,int right) { if(left val val) { res=l1; res->next=merge2Lists(l1->next,l2); } else { res=l2; res->next=merge2Lists(l1,l2->next); } return res; } }}; 3
分治法，不采用递归，复杂度同2，但空间复杂度降低了为O(1)/*------------------------------------------------------------------*/ //分治法，不采用递归，把第二种递归方法转化为非递归方法class Solution3 { //复杂度：O(N*log(K)) 空间复杂度小public: ListNode* mergeKLists(vector & lists) { //分治法，AC，89%) ListNode* result=NULL; if(lists.size()==0) return result; else if(lists.size()==1) return lists[0]; else { int len=lists.size(); while(true) { for(int i=0;i<=len/2;i++) { if(len%2==0&&i val val) { res=l1; res->next=merge2Lists(l1->next,l2); } else { res=l2; res->next=merge2Lists(l1,l2->next); } return res; } }}; 4
使用STL的优先队列，即小顶堆的性质。复杂度：O(NK*log(K)) 堆排序/*------------------------------------------------------------------*///优先队列（其实就是大顶堆排序），使用STL的自动建堆class Solution4 { //复杂度：O(NK*log(K)) 堆排序public: struct cmp{ bool operator()(ListNode *a,ListNode *b){ //大的在下，小的在上 return a->val>b->val; } }; ListNode* mergeKLists(vector & lists) { ListNode* result=NULL; if(lists.size()==0) return result; else if(lists.size()==1) return lists[0]; priority_queue ,cmp> queue; for(int i=0;i next=temp;//以后的元素都赋给prev->next prev=prev->next;//prev指向它的下一个元素 } if(temp->next!=NULL)//也就是说temp所在的链表还有元素（temp后面的），就把temp后面的元素加入堆中 { queue.push(temp->next); } } return head;//返回指向第一个元素的指针，也就是返回已经排好序的一大串 }}; 5
自己写的小顶堆，不适用STL的。复杂度同4./*------------------------------------------------------------------*///自己建立堆class Solution { public: ListNode* mergeKLists(vector & lists){ ListNode* result=NULL; if(lists.size()==0) return result; else if(lists.size()==1) return lists[0]; vector heap; for(int i=0;i next=temp; prev=prev->next; } if(temp->next!=NULL) { heap_push(heap,temp->next);//加入新元素，自己写这个函数 } } return head; }private: void makeheap(vector &heap) { for(int i=heap.size()/2;i>0;i--)//堆的序号是从1到heap.size()/2 minHeap(heap,i); }void minHeap(vector &heap,int i)//以i为父节点的子树,建立堆{ int lchild=2*i;//i的左孩子节点序号(序号是从1开始) int rchild=2*i+1;//i的右孩子节点序号 int least=i;//临时变量 if(lchild<=heap.size()&&heap[lchild-1]->val val) { least=lchild; } if(rchild<=heap.size()&&heap[rchild-1]->val val) { least=rchild; } //上述两个if是为了获取i节点，i节点的左右孩子三个中最小的那个，下标存到least if(least!=i)//不是父节点i { swap(heap[i-1],heap[least-1]); minHeap(heap,least);//避免调整之后以least为父节点的子树不是堆（因为此时左右子树的一个和父节点换了，那么换后的左右子树那个还要继续调整） }}void swap(ListNode *&a,ListNode *&b)//指针作为形参传递，加引用才能在调用时更改其值！（这儿困惑了好久，一直不明白）{ ListNode * c; c=a; a=b; b=c;}void heap_push(vector &heap,ListNode * p){ heap.push_back(p);//把该链表加入heap中 //minHeap(heap, 1); for(int child=heap.size(),parent=child/2;parent>0;child=child/2,parent=child/2) //因为添加的元素是最后一个，所以只需从底部向上进行判断 { if(heap[child-1]->val val) swap(heap[child-1],heap[parent-1]); }}ListNode*heap_pop(vector &heap)//删除堆顶的元素，并返回{ swap(heap[0],heap[heap.size()-1]);//把最后一个和第一个交换，是为了方便删除第一个 ListNode* p=heap[heap.size()-1];//获取最后一个 heap.pop_back(); minHeap(heap,1);//重新建立堆（第一步交换后，要重新调整顺序），因为现在的第一个是原来的最后一个，所以要从头到尾堆排序一下 return p;}}; 总结：2，3，4，5都AC了，1 TLE。另外自己写小顶堆，错误很多，好多没考虑清楚的，调试了好久，不过写一次确实能锻炼能力。
转载地址：http://kexvi.baihongyu.com/