# Merge k sorted lists

Posted: 28 Dec, 2020

Difficulty: Hard

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

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

Approach 2

Approach 3

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

SIMILAR PROBLEMS

# Insertion In Circular Linked List

Posted: 21 Apr, 2022

Difficulty: Easy

# Insertion In A Singly Linked List

Posted: 22 Apr, 2022

Difficulty: Easy

# Deletion In Doubly Linked List

Posted: 22 Apr, 2022

Difficulty: Easy

# Insertion In Doubly Linked List

Posted: 24 Apr, 2022

Difficulty: Easy

# Min Heap

Posted: 5 May, 2022

Difficulty: Moderate