题目描述：
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
解题分析：
解题思路很简单，就是先两两排序，不断减小链表数量，最后将所有数组织成一个有序链表
具体代码：
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9 public class Solution { 10 public static ListNode mergeKLists(ListNode[] lists) { 11 if(lists.length==0) 12 return null; 13 if(lists.length==1) 14 return lists[0]; 15 int from=0; 16 int to=lists.length-1; 17 //两两排序时使用类似二分查找的方法缩小时间复杂度 18 while(from!=to){ 19 //from+to等于偶数 20 if(((from+to)&1)==0){ 21 int mid=(from+to)>>1; 22 for(int i=0;i<mid;i++){ 23 lists[i]=mergeTwoLists(lists[i], lists[mid+1+i]); 24 } 25 to=mid; 26 } 27 else{ 28 int mid=(from+to)>>1; 29 for(int i=0;i<=mid;i++){ 30 lists[i]=mergeTwoLists(lists[i], lists[mid+1+i]); 31 } 32 to=mid; 33 } 34 } 35 return lists[0]; 36 } 37 //和并两个链表的方法 38 public static ListNode mergeTwoLists(ListNode head1, ListNode head2) { 39 if(head1==null) 40 return head2; 41 if(head2==null) 42 return head1; 43 ListNode head=null; 44 ListNode current=null; 45 if(head1.val<=head2.val){ 46 head=head1; 47 head1=head1.next; 48 head.next=null; 49 } 50 else{ 51 head=head2; 52 head2=head2.next; 53 head.next=null; 54 } 55 current=head; 56 while(head1!=null&&head2!=null){ 57 if(head1.val<=head2.val){ 58 current.next=head1; 59 current=current.next; 60 head1=head1.next; 61 current.next=null; 62 } 63 else{ 64 current.next=head2; 65 current=current.next; 66 head2=head2.next; 67 current.next=null; 68 } 69 } 70 if(head1!=null){ 71 current.next=head1; 72 } 73 if(head2!=null){ 74 current.next=head2; 75 } 76 return head; 77 } 78 }