Leetcode – 23. Merge k Sorted Lists

Reading Time: 3 minutes

There are so many ways to solve this problem. Let’s look at some of them:

  1. Iterate through all the nodes in all the k lists and dump the values in an array, then sort the array, iterate through the sorted array, generate the linked list and return the head. This obviously doesn’t sound like an efficient algorithm.
  2. We can use a Min Heap with max size k. We insert the heads of the linked lists into the heap and as we remove from the heap, we should insert the next element from the list that had it’s element evicted from the heap. Using a heap will give us a time complexity of O(lg k) for removing and inserting. But, there are N removals and insertions therefore the time complexity will be O(N lg k)
  3. We can solve this in linear time by merging 2 lists at a time.

We are going to take the third approach discussed above. Let’s consider that we have 5 linked lists represented by A, B, C, D, E. Let the notation represent the merger of two lists.

The initial array is:

A B C D E

In our first iteration, we will remove the lists A and B, merge them and put them back in the array. At this point our array will look like:

C D E A•B

In the second iteration, we will remove the lists C and D, merge them and put them back in the array. At this point our array will look like:

E A•B C•D

In the third iteration, we will remove the lists E and A•B, merge them and put them back in the array. At this point our array will look like:

C•D A•B•E

In the fourth iteration, we will remove the lists C•D and A•B•E, merge them and put them back in the array. At this point our array will look like:

A•B•E•C•D

At this point, we have merged all k lists in k-1 iterations. Basically we keep iterating until the array containing the heads of the k linked lists has only one element. At this point we are guaranteed that this is the merged list.

This problem is listed as hard on Leetcode and at first it doesn’t seem so. While the actual algorithm to implement this is actually pretty easy, there are several conditions that one needs to take care of.

Let’s look at them one by one.

  1. What do you do if the array containing the heads of the lists is empty?
  2. What if the the size of the array containing the heads has only one element?
  3. When we pull the first 2 elements out of the array, there are chances one of them, or both of them will be nil. If the first one is nil, just remove it from the array and continue the loop. If the second is nil, remove it from the list and put the first one back in the list so that it is considered for a merge in a future operation and continue the loop.
  4. When merging two arrays, what if the 2 heads are pointing to the same instance?
  5. When merging two arrays, you have to account for one list being shorter than the other. So before returning, we must take the longer list and append it’s elements to the result list.
     

A guaranteed solution is only possible iff the above conditions are satisfied.

Time Complexity: Merging two lists take O(n) time where n is the total number of elements in the 2 lists. In our case we are merging two lists k-1 times which gives us a total time complexity of O(kN) where N is the number of all elements

Space Complexity: I am creating a temporary array to hold the heads which will be O(k) space.

Solution available on Github.

Mohit AthwaniLeetcode – 23. Merge k Sorted Lists

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.