Merge K Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Merge Tow Sorted Lists is quiet easy to implement, but how to merge k sorted list? I have searched several methods for this questions in Google, I think the best method to implement this question is to use the PriorityQueue, so now let's discuss it in detail:

Solution:
First, the steps of this method is:
1. Build up a min heap of the k head nodes of given lists.
2. Create a ListNodeComparator to make sure the smallest one(the head of the minHeap) and add its next to heap.
3. Repeat until all nodes in lists have been merged into one list.

And here are some details to notice:

1. Since ListNode doesn't have its compare method, we need to provide our own comparator and pass it in during construction time.(return -1 for less-than; return 1 for greater-than; return 0 for equal.)

2. PriorityQueue is an unbounded queue based on heap.

Bottom-Line: we should master how to use the minHeap and how to write a comaprator

Code in JAVA:

public class Merge_k_Sorted_Lists {
 public static class ListNode{
  public int val;
  ListNode next;
  ListNode(int x) {
   val = x;
   next = null;
  }
 }
 //Build a comparator
 private static Comparator listNodeComparator = 
   new Comparator(){

    @Override
    public int compare(ListNode o1, ListNode o2) {
     if (o1.val < o2.val) {
      return -1;
     } else if (o1.val > o2.val) {
      return 1;
     } else {
      return 0;
     }
     
    }
  
 };
 
 public static ListNode mergeKLists(ArrayList lists) {
  if (lists == null || lists.size() == 0) {
   return null;
  }
  Queue heap = new PriorityQueue(lists.size(), listNodeComparator);
  // add element to heap
  for (int i = 0; i < lists.size(); i++) {
   if (lists.get(i) != null) {
    // put the head of each list into heap
    heap.add(lists.get(i));
   }
  }
  
  ListNode dummy = new ListNode(0);
  ListNode tail = dummy;
  while (!heap.isEmpty()) {
   ListNode head = heap.poll();
   tail.next = head;
   tail = head;
   if (head.next != null) {
    heap.add(head.next);
   }
  }
  return dummy.next;
 }
 
}

Analysis and Comparison:

In mergeSort solution, each original list has been touched O(logk) times, where k is the number of lists. That said, each node has been touched O(logk) times. So the total running time is O(Nklogk), where N is the number of each lists.
Note that, for odd cases, as shown above, some list(s) may be touched more than logktimes, but still O(logk) times.

In heapSort solution, only head nodes of lists are kept in the min-heap.
Building up such a heap takes time O(klogk), each following insertion requires O(logk) time and there are at most Nk insertions in total. So the total running time is also O(Nklogk). And space compexity using minHeap reduce from O(n) to O(1).