Two AC java solution using PriorityQueue and Merge Sort


  • 3
    J
    //priorityQueue: NlogK, N = total length
    //two merge: N*logK, in-place
    public ListNode mergeKLists(ListNode[] lists) {
        for(int ct = lists.length; ct > 1; ct = (ct + 1 >> 1)){
            for(int i = 0; i < ct; i += 2){
                lists[i>>1] = mergeTwoLists(lists[i], i + 1 < ct ? lists[i+1] : null);
            }
        }
        return lists.length == 0 ? null : lists[0];
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2){
        if(l1 == null)  return l2;
        else if(l2 == null) return l1;
        if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else{
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
    
    //PriorityQueue
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> q = new PriorityQueue<ListNode>(new Comparator<ListNode>(){
            public int compare(ListNode l1, ListNode l2){
                return ((Integer)l1.val).compareTo(l2.val);
            }
            });
        for(int i = 0; i < lists.length; i++)
            if(lists[i] != null)
                q.add(lists[i]);
        ListNode fake = new ListNode(1), lnode = fake;
        while(!q.isEmpty()){
            ListNode node = q.poll();
            lnode.next = node;
            node = node.next;
            if(node != null)    q.add(node);
            lnode = lnode.next;
        }
        return fake.next;
    }

Log in to reply
 

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