Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Put all lists into a queue, while queue size is bigger than one, pop two lists from queue, merge them to one, and put back to queue. O(n lg k)
Maintain a heap of k elements, with invariant of every lists' top node
For each iteration, pop the top node in the heap at each loop and add a new node from the same original list. O(n lg k)