Leetcode 23: Merge k Sorted Lists

There are a few different ways to solve this. I found the easiest way was to do a merge k-1 times. So you merge the first two lists. Then you merge that merged list with list 3. And repeat that until all lists are merged. That results in O(kN) time and O(1) space.

We improve the speed by either using a heap/priorityqueue or a map to allow us to quickly select the next smallest node out of the current nodes in all the lists. So we add the heads of all the lists to a map with the value as the key. We then remove the smallest (begin of map) and add it to our merged list. Then we add a new map entry of the next node of the node we just processed (if there is one). Repeat that until the map is empty. This results in O(Nlogk) time and O(k) space.

Here is the O(kN) time solution code: https://gist.github.com/adamkorg/665adeec343a9a114e1088833f96dbb8
And here is the O(Nlogk) solution code:

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *