O(nmlogn) Java solution explained with algorithm


  • 0
    L
        //Algorithm: a. Get the min from all lists and add them into a min heap.
        //b. Take the min of all and add to another list.
        //c. Add the next from the List that has been picked up from and repeat picking up
        // the min. Time complexity: n lists of max size m will be: nmlogn  
    
        public ListNode mergeKLists(ListNode[] lists) {
            if(lists==null || lists.length==0) {
                return null;
            }
            
    
            PriorityQueue<ListNodeMarker> minheap = new PriorityQueue<>();
            for(ListNode l : lists) {
                if(l!=null) {
                    minheap.add(new ListNodeMarker(l));
                }
            }
            
            ListNode dummy = new ListNode(-1);
            ListNode dummyIt = dummy;
            while(!minheap.isEmpty()) {
                //get the min.
                ListNodeMarker marker = minheap.poll();
                dummyIt.next=marker.root;
                dummyIt = dummyIt.next;
                //add the next from this marker.
                ListNode temp = marker.moveNext();
                if(temp!=null) {
                 minheap.add(marker);   
                }
            }
            dummyIt.next=null;
            return dummy.next;
        }
        
        private class ListNodeMarker implements Comparable<ListNodeMarker> {
            private ListNode root;
            
            ListNodeMarker(ListNode root) {
                this.root = root;
            }
            
            ListNode moveNext() {
                if(root!=null) {
                    root = root.next;
                }
                return root;
            }
            
            public int compareTo(ListNodeMarker marker) {
                return Integer.compare(this.root.val,marker.root.val);
            }
        }
    

Log in to reply
 

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