Simple Java solution using binary search,quite straightforward


  • 1
    W
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0)return null;
        int start=0;
        int end=lists.length-1;
        ListNode head=merge(lists,start,end);
        return head;
    }
    
    private ListNode merge(ListNode[] lists, int start, int end){
        if(start==end)return lists[start];
        int mid=(start+end)/2;
        ListNode l1=merge(lists,start,mid);
        ListNode l2=merge(lists,mid+1,end);
        ListNode dummy=new ListNode(0);
        ListNode cur=dummy;
        while(l1!=null&&l2!=null){
            if(l1.val>=l2.val){
                cur.next=l2;
                l2=l2.next;
            }else{
                cur.next=l1;
                l1=l1.next;
            }
            cur=cur.next;
        }
        if(l1==null){
            cur.next=l2;
        }
        if(l2==null){
            cur.next=l1;
        }
        return dummy.next;
    }
    

    Time complexity would be o(nlogn).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.