O(nmlogn) Java solution explained with algorithm

  • 0
        //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 = dummyIt.next;
                //add the next from this marker.
                ListNode temp = marker.moveNext();
                if(temp!=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.