Merge k Sorted Lists Cont… (Slower)

Question: Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Check out the complete question here. And to see the previous approach hop over to this post.

Confession: This is a (significantly)slower approach. Accurate none the less. But if you are looking for a solution that magically finishes in ground breaking runtime, then this is NOT the post you would want to read.

Then why am I posting this you ask? Well, the code works and the approach is surprisingly clean. The algorithm used here is borrowed from the merging two sorted lists solution —

1. Just(sense the sarcasm folks!) maintain a sorted list of these k lists, again in a linked list. (Sorted based on the value at the head of each lists)
2. Keep fetching the list at the head of this list-of-lists
3. Extract the node/value at the head of this list
4. Create a new list (devoid of the extracted value)
5. Insert this new list back into the list-of-lists in the correct position to remain sorted
6. Iterate till you exhaust all the values

And here’s the implementation…

//Approach 2
//Runtime: 165ms (That's CRAZY!)
//Memory usage: 40.3MB
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public class ListOfListNode {
        ListNode list;
        ListOfListNode nextList;
        ListOfListNode(ListNode list){
            this.list = list;
        }
    }
 
 //to insert a list into a sorted list of list 
 //(sorted based on the head of the list)
 private ListOfListNode insertNodeAndSort(ListNode node, ListOfListNode list) {
  //Nothing to check
  //this is assuming that the listOfListNode can have only one null list at the max
  //and that null list will be at the head (first entry)
  if(list==null || (list!=null && list.list==null)) {
   return new ListOfListNode(node);
  }
  //Nothing add
  //empty list should not be added
  if(node==null) {
   return list;
  }
  //if node is smaller than currNode
  //insert node before this node
  if(node.val<list.list.val) {
   ListOfListNode newList = new ListOfListNode(node);
   newList.nextList = list;
   return newList;
  }
  
  //make a working copy of the list
  ListOfListNode currList = list;
  while(currList!=null) {
   ListNode currNode = currList.list;
   if(currList.list==null || currList.nextList==null || currList.nextList.list==null || (currList.list.val<=node.val && currList.nextList.list.val>node.val)) {
    ListOfListNode newListNode = new ListOfListNode(node);
    newListNode.nextList = currList.nextList;
                currList.nextList = newListNode;
    break;
   }
   currList = currList.nextList;
  }
  return list;
 }
 
 public ListNode mergeKLists(ListNode[] lists) {
  ListOfListNode sortedListOfLists = new ListOfListNode(null);
  for(ListNode node : lists) {
   sortedListOfLists = insertNodeAndSort(node, sortedListOfLists);
  }
  ListNode sortedNodes = null;
  ListNode prevNode = null;
  while(sortedListOfLists!=null && sortedListOfLists.list!=null) {
   //BUILD THE FINAL SORTED LIST
   //fetch the head
   ListNode currNode = sortedListOfLists.list;
   if(prevNode!=null) {
    prevNode.next = currNode;
   }
   //the final sorted list has not been initialized yet
   if(sortedNodes==null) {
    sortedNodes = currNode;
   }
   prevNode = currNode;
   
   //RE_CONSTRUCT sortedListOfLists MINUS THE HEAD
   sortedListOfLists = sortedListOfLists.nextList;
   sortedListOfLists = insertNodeAndSort(currNode.next, sortedListOfLists);
  }
  return sortedNodes;
 }
}

Clearly the current approach is almost 3x the previous approach in terms of its runtime! And yet there was some persistence in posting this solution. Primarily for the key lesson learnt — modularization / abstraction! Until next time…

Find more posts here.

Cheers & Chao!