Q: Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Note K could be much larger than N.
I feel this is mostly an optimization challenge. I can think of a few solutions
–Sol1: merge 2nd list into first. Then merge 3rd list into first …
https://leetcode.com/problems/merge-k-sorted-lists/solution/ shows that this has higher runtime cost than the brackets solution.
Reason is, each 2-merge-to-1 must visit every node in both lists. So the first list nodes get visited K times!
There are only (log K) levels in the bracket so any list gets visited that many times.
–Sol3: in-place (inefficient)
We maintain K node-pointers for the K lists (K teams)
We also maintain a pointer to the last-added node in the merged list.
first node in K lists are put into a min-heap. Winner (smallest) team would be the “current list”. Now the winner team offers next node and add it into the heap. Winning team ..
What if N=1 and K is 1 billion?