Merge K Sorted Lists

Let’s continue…

Problem Statement:

Given linked list: 1->2->3->4->5, and n = 2.

After removing

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

Solution One: Brute Force

We iterate all the numbers of all lists, and store them in an array.  After that, we sort the array and transfer the result to a new list. After that, output the final result.

Time Complexity: O(n*log(n)) We construct the array, which takes O(n) time, and sorting the array takes O(n*log(n)) time. n is the number of total nodes in all lists.

Space Complexity: O(n)

Solution Two: Compare Lists by Columns

The general idea is like the picture demonstrated below. We compare all the lists in one column. We first find the smallest number of this column and make it our head node,  then we move this list forward, and compare the new column again, until we find the second smallest element, then we connect our head node to this node. After that, we move forward the second list and continue this progress until all lists are empty.

Note here we do a tiny trick that we always connect the current smallest node to the previous smallest node, so we can make the space complexity O(1).

Time Complexity: O(K*N), N is the length of the longest sub list. K is the number of the lists.

Space Complexity: O(1)

Solution Three: Priority Queue

This idea is based on the Solution Two. In Solution Two, we can see that, each time when we want to find the current smallest element, we need to iterate all the lists, which takes O(K) time. When we find this element, we connect it with previous found nodes, we need O(1) time. Can we do better here?

We can utilize the properties of priority queue to accelerate the searching process. For the first time, we just add all the first elements to our priority queue. We maintain our priority and make sure that the smallest element should always on top (first pop out). If we want the smallest number, we can easily pop the top element out of the priority queue. This operation will take O(log(k)) time because we need to balance the remaining elements and make sure the second smallest on top of the priority queue. The same thing as insert, it takes O(log (k)) time.

The rest of the idea is the same. If one list contains the current smallest element, we pop out that node, and move forward that list one Node ahead.

Time Complexity: O(max(k, n* log(k))), k is the number of sub lists

Space Complexity: O(k)

Solution Four: Combine two

Look at the picture below. Note we are going to merge two lists at one time. We keep dividing the remaining lists into different two pairs, and keep merging them until we are done. For example, in the first iteration, we merge list0 and list1; list2 and list3; list4 and list5. The second iteration, we merge list0 and list2; list4….

We did this trick to reduce total times of merging. The merging process will consumes O(n’), n’ is the average number of all lists. We will do the merging process log(k) times instead of k, so the time complexity is O(n’*log(k)).

Time Complexity: O(n’*log(k))

Space Complexity: (1)

That’s all for today, thanks for reading….