Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Actually we could also utilize the
merge 2 sorted lists methods and a queue to solve this problem but its worst case is really bad, about O(n^2).
Using a minHeap to ensure the worst time complexity O(nlogk). There are several corner cases that should be handled: NULL in the list, no list at all, add the next of the new head.
Always welcome new ideas and
practical tricks, just leave them in the comments!