a) Efficient way would be the use of MinHeaps without bothering about extra space.
Approach: Use of Min Heaps
- Creating a MinHeap (PriorityQueue)
- Inserting the first element of K linked lists.
- Dequeue the top element of Minheap.
- Insert it in the output list.
- Insert the next element from the linked list whose element is removed.
- Repeat until there is no more element left in the MinHeap.
The time complexity of this approach is $O( mK * log_2 K)$.
b) Approach 1: Naive solution
- Initialize the first list of K lists as the Output list.
- Traverse from the second list to the Kth List.
- Insert every node of the currently traversed list into the Output list in a sorted way.
The time complexity of this approach is $O(N^2)$ where N = k*m
Approach 2: Use of Divide & Conquer approach (similar to MERGE procedure of Merge sort)
- Assume each of the K sorted lists of size m as a single module and successively merge two lists at a time up to K.
- Now for the K/2 sorted lists of size 2m, merge two of the lists at a time up to K/2.
- Similarly, there are K/4 sorted lists of size 4m and we merge them.
- Repeat the above process for $log_2 K$
The time complexity of this approach is $O(mK*log_2 K)$ because the outer loop runs log K times and every time it processes m*K elements.
In both of the above approaches, we don’t need any extra space considering the fact that we implement them iteratively and not recursively which will account extra function call stack space.