Merge k sorted lists

Hard
0/120
Average time to solve is 25m
profile
Contributed by
105 upvotes
Asked in companies
MicrosofteBayAmazon

Problem statement

Given 'k' sorted linked lists, each list is sorted in increasing order. You need to merge all these lists into one single sorted list. You need to return the head of the final linked list.


For example:
Input:
3
3
4 6 8
3
2 5 7 
2
1 9

Output:
1 2 4 5 6 7 8 9 

Explanation:
First list is: 4 -> 6 -> 8 -> NULL
Second list is: 2 -> 5 -> 7 -> NULL
Third list is: 1 -> 9 -> NULL
The final list would be: 1 -> 2 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> NULL
Detailed explanation ( Input/output format, Notes, Images )
Input format:
The first line consists of an integer 'k' denoting the number of lists.

Next 2*k lines consists of 'n', the size of linked list and the 'n' space-separated elements on the new line.
Output format:.
The output consists of space-separated elements of the merged sorted list.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1:
2
2
2 6 
2
-5 7 
Sample Output 1:
-5 2 6 7
Explanation for input 1:
First list is: 2 -> 6 -> NULL
Second list is: -5 -> 7 -> NULL
The final list would be: -5 -> 2 -> 6 -> 7 -> NULL
Sample Input 2:
2
3
8 9 11 
2
1 2 
Sample output 2:
1 2 8 9 11 
Constraints:
1 <= 'k' <= 10 ^ 3
1 <= 'n' <= 100
-10 ^ 9  <= 'data' <=  10 ^ 9 

where 'n' is the size of the list.
Time limit: 1 sec.
Hint

Insert elements of all lists into one array. 

Approaches (2)
Naive Approach

Here we will perform a brute force of adding all the nodes in a separate list and then sort it.

  1. Traverse through all the linked lists and add each node in a different array.
  2. Sort the array.
  3. Make a new linked list and add all of the elements of the sorted array.
Time Complexity

O(n * log n), where ‘n’ is the total number of nodes.

 

In the worst case, we are sorting an array of size ‘n’.

Space Complexity

O(n), where ‘n’ is the total number of nodes.

 

In the worst case, we are creating an array of size ‘n’.

Code Solution
(100% EXP penalty)
Merge k sorted lists
Full screen
Console