Java 6ms straightforward recursive solution using mergeTwoLists()


  • 0

    This solution is not the fastest. It will beat 63%. But it is very easy to come up with. I just make use of my solution to mergeTwoLists and recursive call that function. The time complexity is O(nk*log(k)). n is the length of a list and k is the number of list.

    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0) return null;
        if(lists.length==1) return lists[0];
        return helper(lists,0,lists.length - 1);
    }
    
    private ListNode helper(ListNode[] lists, int start, int end){
        if(start==end){
            return lists[start];
        }
        int mid = start + (end-start)/2;
        ListNode lefthead = helper(lists,start,mid);
        ListNode righthead = helper(lists,mid+1,end);
        return mergeTwoLists(lefthead,righthead);
    }
    
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = new ListNode(0);
        dummy.next = curr;
        while(l1!=null||l2!=null){
            if(l1==null||l1!=null&&l2!=null&&l2.val<=l1.val){
                ListNode temp = new ListNode(l2.val);
                l2 = l2.next;
                curr.next = temp;
                curr = curr.next;
                continue;
            }
            if(l2==null||l1!=null&&l2!=null&&l1.val<l2.val){
                ListNode temp = new ListNode(l1.val);
                l1 = l1.next;
                curr.next = temp;
                curr = curr.next;
                continue;
            }
            
        }
        return dummy.next.next;
    }

Log in to reply
 

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