Merge k sorted lists
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

Question

Merge k sorted lists

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.

Accepted Answer

A Simple Solution is to initialize the result as the first list. Now traverse all lists starting from the second list. Insert every node of the currently traversed list into the result in a sorted way.

Accepted Answer

Compare one by one and find smallest

The idea is to pick the nodes of the final list one by one, by comparing heads of all K lists.
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.
Repeat step 2, until all lists get empty.
In this way, we get our final list.

Space Complexity: O(1)Explanation:

O(1).

In the worst case, we are taking constant space, as we are only adding elements of all ‘K’ lists into 1 final list.

Time Complexity: OtherExplanation:

O(N * K), where ‘N’ is the total number of nodes and ‘K’ is the number of lists.

In the worst case, we are comparing the head node of all ‘K’ lists for each node of the final list.

Accepted Answer

Naive Approach

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

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

Space Complexity: O(n)Explanation:

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

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

Time Complexity: O(nlogn)Explanation:

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

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

Accepted Answer

Using Priority Queue

The idea is to use priority queue to reduce searching time for list with smaller head value.
We will maintain a priority queue for the head node of K list.
The top of the queue gives the nodes with smaller value.
We will add this head node into our final list and move the head pointer of that list to the next node of that list and update it in our queue.
We will repeat step 3 and 4, until the queue becomes empty.

Space Complexity: OtherExplanation:

O(K), where ‘K’ is the number of lists.

In the worst case, we are making a priority queue of size ‘K’.

Time Complexity: OtherExplanation:

O(N * log K), where ‘N’ is the total number of nodes and ‘K’ is the number of lists.

In the worst case, we are finding the smallest head node in the queue which takes log K time. And we perform this operation for all ‘N’ nodes, so, overall complexity becomes O(N * log K).

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:

Output format:

Note:

Constraints:

Top Nagarro SDE interview questions & answers

Popular interview questions of SDE