链表

public class LeetCode23 {

    public static void main(String[] args) {
        ListNode list1= new ListNode(1);
        list1.next=new ListNode(4);
        list1.next.next =new ListNode(5);

        ListNode list2= new ListNode(1);
        list2.next=new ListNode(3);
        list2.next.next =new ListNode(4);

        ListNode list3= new ListNode(2);
        list3.next=new ListNode(6);
        ListNode[] lists=new ListNode[]{list1,list2,list3};

        ListNode ret=(new Solution23()).mergeKLists(lists);

        while (ret!=null){
            System.out.printf(ret.val+",");
            ret=ret.next;
        }

    }

}
class Solution23 {

    public ListNode mergeKLists(ListNode[] lists){
       if(lists.length ==0){
           return null;
       }

       if(lists.length ==1){
           return lists[0];
       }

       if (lists.length ==2){
           return mergeTwoLists(lists[0],lists[1]);
       }

       int mid= lists.length/2;

       ListNode[] l1= new ListNode[mid];
       for (int i=0;i< mid;i++){
           l1[i] = lists[i];
       }
       ListNode[] l2= new ListNode[lists.length-mid];
       for (int j=0,k=mid;k<lists.length;k++,j++){
           l2[j]= lists[k];
       }
        return  mergeTwoLists(mergeKLists(l1),mergeKLists(l2));
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        ListNode head=null;
        if(l1.val<=l2.val){
            head = l1;
            head.next = mergeTwoLists(l1.next,l2);
        }else{
            head = l2;
            head.next= mergeTwoLists(l1,l2.next);
        }
        return head;
    }

}