Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Solution: merge sort. use an extra list to save.
Iterative find the min element in each loop: O(KN)


Build a heap in the first run, then use heap insert/delete: O(N logK)

Redo it in Mar. 17, 2014

Comments

Popular posts from this blog

Maximum Gap

[ITint5] Maximum Subarray for a Circular Array

[CC150] Chapter 4 Trees and Graphs