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.
Approach 1
  1. The idea is to pick the nodes of the final list one by one, by comparing heads of all K lists.
  2. Pick the list with the smallest head value, add that node to the final node and move the head pointer of that list one node ahead.
    • Say you have chosen the list  A -> B-> C -> NULL. with the smallest head value. And currently your final list is E -> F -> G -> H-> NULL.
    • Then you simply disconnect the node A from list A -> B -> C-> NULL, so it becomes B -> C-> NULL. And A to your final list E -> F -> G -> H -> A -> NULL.
  3. Repeat step 2, until all lists get empty.
  4. In this way, we get our final list.
Try Problem