Update appNew update is available. Click here to update.

Merge k sorted lists

Posted: 28 Dec, 2020
Difficulty: Hard

PROBLEM STATEMENT

Try Problem

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.

Input format:
The first line of input contains an integer 'T' denoting the number of queries or test cases. 

The first line of each test case consists of an integer 'K' denoting the number of lists.

Next 'K' lines for each test case will have space separated integers and ith line will have elements of the ith linked list separated by a single space and terminated by -1.
Output format:
For each test case, print a single line containing space-separated denoting the elements of the merged sorted list. The elements of the linked list must be separated by a single space and terminated by -1.

The output of each test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
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.