[leedcode 23] Merge k Sorted Lists
4130 ワード
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
// , , k , kn O(knk)
// ,T(k)=2T(k/2)+O(nk); O(nklogk)
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length<1) return null;
if(lists.length==1) return lists[0];
return merge1(lists,0,lists.length-1);
}
public ListNode merge1(ListNode[] lists,int start,int end){
if(start<end){
int mid=(start+end)/2;
ListNode l1=merge1(lists,start,mid);
ListNode l2=merge1(lists,mid+1,end);
return merge2(l1,l2);//
}else{
return lists[start];
}
}
public ListNode merge2(ListNode l1,ListNode l2){
ListNode newHead=new ListNode(-1);
ListNode temp=newHead;
while(l1!=null&&l2!=null){
if(l1.val<l2.val){
temp.next=l1;
l1=l1.next;
}else{
temp.next=l2;
l2=l2.next;
}
temp=temp.next;
}
if(l1!=null){
temp.next=l1;
}
if(l2!=null){
temp.next=l2;
}
return newHead.next;
}
}