[c++]合并排序多个已排好序的单项链表

题目来源：Leetcode

题目描述：

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

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

思路：不断合并两个链直到所有合并完成 $O (k N)$

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* mergeKLists(vector<ListNode*>& lists) {
12         ListNode* r=NULL;
13         if(lists.size()==0) return r;
14         for(int i=0;i<lists.size();++i)
15         {
16             r=mergeTwo(r,lists[i]);
17         }
18         return r;
19     }
20     ListNode* mergeTwo(ListNode *r1,ListNode *r2)
21     {
22         if(r1==NULL) return r2;
23         if(r2==NULL) return r1;
24         if(r1->val<=r2->val) { r1->next=mergeTwo(r1->next,r2); return r1;}
25         else { r2->next=mergeTwo(r1,r2->next); return r2;}
26     }
27 };

附加思路：将所有链表不断切半到只剩下两个，将其合并，回到上一层，将其合并

附加思路：先遍历所有链表把他们的值放入一个数组，放的时候就排序好的放，然后把链表连起来成一个链表，把数组的值依次赋值

Time complexity :

Collecting all the values costs
A stable sorting algorithm costs
Iterating for creating the linked list costs

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* mergeKLists(vector<ListNode*>& lists) {
12         ListNode* r=NULL;
13         if(lists.size()==0) return r;
14         vector<int> m;
15         for(int i=0;i<lists.size();++i)
16         {
17             ListNode* t=lists[i];
18             while(t!=NULL)
19                 {m.push_back(t->val);t=t->next;}
20         }
21         QuickSort(m,0,m.size()-1);
22         r=lists[0];
23         int j=0;
24         for(int i=0;i<lists.size();++i)
25         {
26             ListNode* t=lists[i];
27             while(t->next!=NULL)
28             {
29                 t->val=m[j];
30                 ++j;
31             }
32             t->val=m[j];
33             if(i+1<lists.size()) t->next=lists[i+1];
34         }
35         return r;
36     }
37     void QuickSort(vector<int>& list,int p,int r)//快排
38     {
39         
40         if(p<r)  {
41         int q=Part(list,p,r);
42         QuickSort(list,p,q-1);
43         QuickSort(list,q,r);
44         }
45     }
46     int Part(vector<int>& list,int p,int r)
47     {
48         int i=p,j=r+1;
49         int x=list[p];
50         while(1)
51         {
52             while(list[++i]<x&&i<r);
53             while(list[--j]>x);
54             if(i>=j) break;
55             int temp=list[i];
56             list[i]=list[j];
57             list[j]=temp;
58         }
59         list[p]=list[j];
60         list[j]=x;
61         return j;
62     }
63 };

Run Code Status:

Runtime Error

原创供学习参考使用，转载请注明出处http://www.cnblogs.com/cuphoria/ @jm_epiphany