题目：

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

思路1：

依次归并排序，首先归并前两个，然后归并完成的链表依次和剩下的链表进行归并排序

时间复杂度为O(m*n)

代码：

public static ListNode mergeKLists1(ListNode[] lists){
int len = lists.length;
if(len == 0){
return null;
}else{
if(len == 1){
return lists[0];
}else{
ListNode headl = new ListNode(-1);
ListNode head1 = lists[0], head2 = lists[1];
for(int i=0; i < len-1; i++){
if(head1 == null){
headl.next = head2;
}else{
if(head2 == null){
headl.next = head1;
}else{
//测量head1的链表长度
int len1 = 0;
ListNode ptr = head1;
while(ptr != null){
len1++;
ptr = ptr.next;
}

//测量head2的长度
int len2 = 0;
ptr = head2;
while(ptr != null){
len2++;
ptr = ptr.next;
}

ptr = headl;
ListNode ptr1 = head1, ptr2 = head2;
for(int j=0; j< len1+len2; j++){
if(ptr1 !=null && ptr2 != null){
if(ptr1.val <= ptr2.val){
ptr.next = ptr1;
ptr1 = ptr1.next;
ptr = ptr.next;
}else{
ptr.next = ptr2;
ptr2 = ptr2.next;
ptr = ptr.next;
}
}else{
if(ptr1 == null){
ptr.next = ptr2;
ptr2 = ptr2.next;
ptr = ptr.next;
}else{
ptr.next = ptr1;
ptr1 = ptr1.next;
ptr = ptr.next;
}
}
}
head1 = headl.next;
if(i+2 <= len-1){
head2 = lists[i+2];
}else{
break;
}
}//else(head1!=null && head2 != null)
}
} //for(int i=0; i < len-1; i++)
return headl.next;
}
}
}

思路2：

分治法

两两归并，递归调用即可。

因为每个链表都已经排序完成了，因此可以把链表数组看成一个待归并排序的数组，对之采用归并排序即可。

时间复杂度为O(n)

AC通过

代码：

public static ListNode mergeKLists(ListNode[] lists){
return mergeKLists(lists, 0, lists.length-1);
}

//分治法果然有效
public static ListNode mergeKLists(ListNode[] lists, int start, int end){
if(start == end){
return lists[start];
}
if(start > end){
return null;
}
int mid = (start + end)/2;
ListNode head1 = mergeKLists(lists, start, mid);
ListNode head2 = mergeKLists(lists, mid+1, end);
ListNode headl = new ListNode(-1);
ListNode ptr = headl;
while(head1 != null && head2 != null){
if(head1.val <= head2.val){
ptr.next = head1;
head1 = head1.next;
ptr = ptr.next;
}else{
ptr.next = head2;
head2 = head2.next;
ptr = ptr.next;
}
}

while(head1 != null){
ptr.next = head1;
head1 = head1.next;
ptr = ptr.next;
}

while(head2 != null){
ptr.next = head2;
head2 = head2.next;
ptr = ptr.next;
}

return headl.next;
}