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 }
下面就是这道题的解法，跟上面的方法一样一样的，就是在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 }
更多Mergesort的讲法请参考：http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/04MergeQuick.pdf
