Straight forward nlog(n) Java code using basic data structure (Updated)


  • 0
    T
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0) return null;
        int len=lists.length;
        while(len>1){
            for(int i=0;i<len-1;i+=2){
                ListNode l1=lists[i];
                ListNode l2=lists[i+1];
                ListNode head=new ListNode(0);
                ListNode tmp=head;
                while(l1!=null||l2!=null){
                    if(l1==null) {
                        tmp.next=l2;
                        break;
                    }
                    if(l2==null){
                        tmp.next=l1;
                        break;
                    }
                    if(l1.val<l2.val){
                        tmp.next=l1;
                        l1=l1.next;
                        tmp=tmp.next;
                    }
                    else{
                        tmp.next=l2;
                        l2=l2.next;
                        tmp=tmp.next;
                    }
                }
                head=head.next;
                lists[i/2]=head;
            }
            if(len%2==0){
                len=len/2;
            }
            else{
                lists[len/2]=lists[len-1];
                len=len/2+1;
            }
        }
        return lists[0];
    }

Log in to reply
 

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