 New update is available. Click here to update.

# Merge k sorted lists

Contributed by
Sounak Majumder
Last Updated: 23 Feb, 2023
Hard 0/120
Avg time to solve 25 mins
Success Rate 65 % Share 28 upvotes

## 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.

Detailed explanation ( Input/output format, Notes, Images ) ##### Constraints:
``````1 <= T <= 10
0 <= K <= 10 ^ 3
0 <= length of lists <= 100
(-10 ^ 9) <= value of list elements <= (10 ^ 9) && value of list elements != -1.

Time limit: 1 sec.
``````
##### Sample Input 1:
`````` 2
3
4 6 8 -1
2 5 7 -1
1 9 -1
2
2 6 -1
-5 7 -1
``````
##### Sample Output 1:
`````` 1 2 4 5 6 7 8 9 -1
-5 2 6 7 -1
``````
##### Explanation for input 1:
``````For first test case:
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

For second test case:
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 -1
1 2 -1
-1
1
1 5 6 8 10 -1
``````
##### Sample output 2:
``````1 2 8 9 11 -1
1 5 6 8 10 -1
``````  Auto Console