K-way Merge

Question 1

23. Merge k Sorted Lists

Problem Statement
Given an array of ‘K’ sorted LinkedLists, merge them into one sorted list.
Example 1:
Input: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4]

Output: [1, 2, 3, 3, 4, 6, 6, 7, 8]
TC – O(N * logK)
SC – O(K)

Answer 1

Pseudo code:

1. Declare min-heap.
2. We can insert the first element of each array in a Min Heap.
3. After this, we can take out the smallest (top) element from the heap and add it to the merged list.
4. After removing the smallest element from the heap, we can insert the next element of the same list into the heap.
5. We can repeat steps 2 and 3 to populate the merged list in sorted order.

Takeaway:

1. Use min-heap
2. Carefully modify the current and head node of resultant list.