题目：
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
题解：
Merge k sorted linked list就是merge 2 sorted linked list的变形题。
而且我们很自然的就想到了经典的Merge Sort，只不过那个是对数组进行sort。而不同的地方，仅仅是Merge两个list的操作不同。
这里来复习一下Merge Sort(对于数组操作），参考Wikipedia：
归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。
归并操作的过程如下：
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
| 最差時間複雜度 | |
|---|---|
| 最優時間複雜度 | |
| 平均時間複雜度 | |
| 最差空間複雜度 |
Merge Sort 对数组操作的Java代码为：
1 public int[] mergeSort(int[] arr){
2 if(arr.length<2||arr == null)
3 return arr;
4
5 MSort(arr,0,arr.length-1);
6 }
7
8 public int[] MSort(int[] arr, int low, int high){
9 if(low < high){
10 int mid = (low+high)/2;
11 int[] left = MSort(arr,low,mid);
12 int[] right = MSort(arr,mid+1,high);
13 return mergeTwoList(left,right);
14 }
15 }
16
17
18 public int[] mergeTwoList(int[] A, int[] B) {
19 int[] C = new int[A.length + B.length];
20 int k = 0;
21 int i = 0;
22 int j = 0;
23 while(i < A.length && j < B.length) {
24 if (A[i] < B[j])
25 C[k++] = A[i++];
26 else
27 C[k++] = B[j++];
28 }
29 while (i < A.length)
30 C[k++] = A[i++];
31 while (j < B.length)
32 C[k++] = B[j++];
33 return C;
34 }
2 if(arr.length<2||arr == null)
3 return arr;
4
5 MSort(arr,0,arr.length-1);
6 }
7
8 public int[] MSort(int[] arr, int low, int high){
9 if(low < high){
10 int mid = (low+high)/2;
11 int[] left = MSort(arr,low,mid);
12 int[] right = MSort(arr,mid+1,high);
13 return mergeTwoList(left,right);
14 }
15 }
16
17
18 public int[] mergeTwoList(int[] A, int[] B) {
19 int[] C = new int[A.length + B.length];
20 int k = 0;
21 int i = 0;
22 int j = 0;
23 while(i < A.length && j < B.length) {
24 if (A[i] < B[j])
25 C[k++] = A[i++];
26 else
27 C[k++] = B[j++];
28 }
29 while (i < A.length)
30 C[k++] = A[i++];
31 while (j < B.length)
32 C[k++] = B[j++];
33 return C;
34 }
下面就是这道题的解法，跟上面的方法一样一样的，就是在mergeTwoList时候是对linkedlist做，套用Merge 2 sorted list解法即可，代码如下：
1 public ListNode mergeKLists(ArrayList<ListNode> lists) {
2 if(lists==null || lists.size()==0)
3 return null;
4 return MSort(lists,0,lists.size()-1);
5 }
6
7 public ListNode MSort(ArrayList<ListNode> lists, int low, int high){
8 if(low < high){
9 int mid = (low+high)/2;
10 ListNode leftlist = MSort(lists,low,mid);
11 ListNode rightlist = MSort(lists,mid+1,high);
12 return mergeTwoLists(leftlist,rightlist);
13 }
14 return lists.get(low);
15 }
16
17
18 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
19 if(l1==null)
20 return l2;
21 if(l2==null)
22 return l1;
23
24 ListNode l3;
25 if(l1.val<l2.val){
26 l3 = l1;
27 l1 = l1.next;
28 }else{
29 l3 = l2;
30 l2 = l2.next;
31 }
32
33 ListNode fakehead = new ListNode(-1);
34 fakehead.next = l3;
35 while(l1!=null&&l2!=null){
36 if(l1.val<l2.val){
37 l3.next = l1;
38 l3 = l3.next;
39 l1 = l1.next;
40 }else{
41 l3.next = l2;
42 l3 = l3.next;
43 l2 = l2.next;
44 }
45 }
46
47 if(l1!=null)
48 l3.next = l1;
49 if(l2!=null)
50 l3.next = l2;
51 return fakehead.next;
52 }
2 if(lists==null || lists.size()==0)
3 return null;
4 return MSort(lists,0,lists.size()-1);
5 }
6
7 public ListNode MSort(ArrayList<ListNode> lists, int low, int high){
8 if(low < high){
9 int mid = (low+high)/2;
10 ListNode leftlist = MSort(lists,low,mid);
11 ListNode rightlist = MSort(lists,mid+1,high);
12 return mergeTwoLists(leftlist,rightlist);
13 }
14 return lists.get(low);
15 }
16
17
18 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
19 if(l1==null)
20 return l2;
21 if(l2==null)
22 return l1;
23
24 ListNode l3;
25 if(l1.val<l2.val){
26 l3 = l1;
27 l1 = l1.next;
28 }else{
29 l3 = l2;
30 l2 = l2.next;
31 }
32
33 ListNode fakehead = new ListNode(-1);
34 fakehead.next = l3;
35 while(l1!=null&&l2!=null){
36 if(l1.val<l2.val){
37 l3.next = l1;
38 l3 = l3.next;
39 l1 = l1.next;
40 }else{
41 l3.next = l2;
42 l3 = l3.next;
43 l2 = l2.next;
44 }
45 }
46
47 if(l1!=null)
48 l3.next = l1;
49 if(l2!=null)
50 l3.next = l2;
51 return fakehead.next;
52 }
更多Mergesort的讲法请参考：http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/04MergeQuick.pdf
讲的挺好的