Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Intuition & Algorithm
As for sorting, you can refer here for more about sorting algorithms.
Complexity Analysis
Time complexity : where is the total number of nodes.
Space complexity : .
Algorithm
!?!../Documents/23_Merge_lists.json:1000,563!?!
Complexity Analysis
Time complexity : where is the number of linked lists.
Space complexity :
Algorithm
Almost the same as the one above but optimize the comparison process by priority queue. You can refer here for more information about it.
Complexity Analysis
Time complexity : where is the number of linked lists.
Space complexity :
Algorithm
Convert merge lists problem to merge 2 lists () times. Here is the merge 2 lists problem page.
Complexity Analysis
Time complexity : where is the number of linked lists.
Space complexity :
Intuition & Algorithm
This approach walks alongside the one above but is improved a lot. We don't need to traverse most nodes many times repeatedly
Pair up lists and merge each pair.
After the first pairing, lists are merged into lists with average length, then , and so on.
Repeat this procedure until we get the final sorted linked list.
Thus, we'll traverse almost nodes per pairing and merging, and repeat this procedure about times.
Complexity Analysis
Time complexity : where is the number of linked lists.
Space complexity :
Analysis written by: @Hermann0