LeetCode problem #23–Merge k sorted lists (JavaScript)

In this LeetCode challenge, we’re given an array of LinkedList elemenets, and asked to return a single LinkedList, containing all of the ListNodes contained within the supplied LinkedList elements, ordered. In other words, we must merge all of the LinkedList objects together, and then sort them.

For most of these solutions, we’ll be using the recursion based LinkedList merger that we created for LeetCode challenge 21, “Merge two sorted lists”.

Solution #1: Merging all LinkedList objects into the first

This solution is probably the easiest to understand, but also the least efficient. Armed with our merge function, it’s fairly trivial to simply loop through all of the provided LinkedList elements, and merge their contents into the first LinkedList. The merging function takes care of sorting, so we’re left with a fully merged, ordered LinkedList.

The problem with this solution is efficiency. Because our merge operation is constantly being carried out on the ever-growing first LinkedList, it’s getting bigger and bigger each time. It would be much more efficient to merge smaller LinkedList elements together, and then to merge their outputs together and so on, so that’s exactly what we’ll look at next.

Solution #2: Recursive merging

In this solution, we pass a recursive function our array of LinkedList objects. That function then calculates the middle point, and calls itself again on both the left and middle, and the right + 1 and middle, or if there are insufficient LinkedLists remaining, it simply returns what it was given.

What this means is that we end up calling the function on every pair of LinkedLists, merging them together as we go. Therefore by the time the recursive function has worked its way back all the way to the top, we’re left with a single ordered LinkedList.

To use an example, let’s say we have 3 LinkedLists. We pass the function those lists, and it creates 2 merge-pairs; 1 + 2, and 3 + nothing. It then merges 1 with 2, and 3 with nothing, then it steps back and merges the combined 1+2 with 3+nothing, giving us a single, ordered LinkedList.

Solution #3: Convert to an array

I’ll admit that this method is somewhat of a cheat, but it does work, and it works quickly too. What we do here is we traverse every provided LinkedList, adding their values to an overall array. We then order that array, and convert it to a new LinkedList.

Note that the way we convert the array to a LinkedList is to do it in reverse order. This is because it allows us to create the last ListNode, which points to nothing, and then to create the second-to-last ListNode, which points to the last, and then the third-to-last ListNode, which points to the second-to-last, and then… well you get the idea.