题解 | #合并k个已排序的链表#
合并k个已排序的链表
http://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
分治法，先合并left-mid，再合并mid+1-right,然后再将两边合并，注意递归返回的条件
/**
* Definition for singly-linked list.* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
import java.util.*;
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
// ListNode dummy=new ListNode(0);
// ListNode p1=dummy;
// int n=lists.size();
// ListNode[] pointer=new ListNode[n];
// for(int i=0;i<n;i++){
// pointer[i]=lists.get(i);
// }
// while(true){
// int min=Integer.MAX_VALUE;
// int memo=-1;
// for(int j=0;j<n;j++){
// if(pointer[j]!=null)
// {if(pointer[j].val<=min){
// min=pointer[j].val;
// memo=j;
// }
// }
// }
// if(memo==-1)
// break;
// dummy.next=pointer[memo];
// dummy=dummy.next;
// pointer[memo]=pointer[memo].next;
// }
// dummy.next=null;
// return p1.next;
return merge(lists,0,lists.size()-1);
}
ListNode merge(ArrayList<ListNode> lists,int left,int right){
if(left==right){
return lists.get(left);
}
else if(left>right){
return null;
}
int mid=(left+right)/2;
ListNode resL=merge(lists,left,mid);
ListNode resR=merge(lists,mid+1,right);
return mergeTowList(resL,resR);
}
ListNode mergeTowList(ListNode l1,ListNode l2){
if(l1==null){
return l2;
}
else if(l2==null){
return l1;
}
ListNode dummy=new ListNode(0);
ListNode p1=dummy;
while(l1!=null&&l2!=null){
if(l1.val<l2.val)
{
dummy.next=l1;
l1=l1.next;
}
else
{
dummy.next=l2;
l2=l2.next;
}
dummy=dummy.next;
}
if(l1==null){
dummy.next=l2;
}
else if(l2==null){
dummy.next=l1;
}
else
dummy.next=null;
return p1.next;
}
}
