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
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
Post a Comment