## Sample Example

We are given 3 sorted lists as shown in the diagram below(K = 3), the resultant linked list after merging the 3 sorted lists is the answer.

Recommended Topic, __Floyds Algorithm__

## Naive Approach

Now we will discuss the** brute-force approach** to Merge K sorted linked lists.

Declare the Node structure and write the function to create and return the node.

â¬‡

Put all elements from the different linked lists into a single list.

â¬‡

Sort the single list.

Time Complexity = O(n log n).

This is the time taken to sort.

Space Complexity = O(n).

We bring a priority queue into the picture to minimize our time from O(n log n) to O(n log k).

Declare a k-length priority queue.

â¬‡

Insert the first element of all k-linked lists into the priority queue.

â¬‡

Pop an element from the priority queue. Check if the popped element is not the last element in a linked list.

â¬‡

If the popped element is not the last element, then pop its next element. Insert in the priority queue and heapify it.

â¬‡

If the popped element is the last element, then pop the next element of the priority queue. Repeat the above steps for all elements.

Time Complexity = O(n log K).

Space Complexity = O(K).

Example:

Lists given are: {1,2,3}, {7,8,9}, {4,5,6}

No of lists=3.

Therefore, make a priority queue of size 3.

Insert the top element from each list and sort in increasing order. i.e: 1,4,7.

Pop 1.

Answer list: 1

Check if 1->next == NULL?

No, 1->next=2. Pop 2 and heapify.

Answer list: 1 2

So priority queue now becomes 2,4,7.

Repeat this for 3.

Priority queue: 3,4,7

Answer list: 1 2 3

3->next==NULL.

So, after popping 3, leave the priority queue as it is.

Priority queue: 4,7

Repeat steps for 4 and so on we will get our answer list.

## Optimised Approach

The best approach to Merge K sorted linked lists is using the divide and conquer method.

Declare two variables. One at the starting list, say i, and the other at the ending list, tell j.

â¬‡

Repeat until one list is left.

â¬‡

Merge List i with List j, sort it, and store the merged list in List i.

â¬‡

For the next pair, increment starting position and decrement the ending position.

â¬‡

If all pairs are merged, update the last list.

**Time complexity: **O(N*log K).

**Space Complexity: **O(N).

N: No of elements in each list.

K: No of linked lists.

Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.

And solve some related problems on the linked list.

merge-k-sorted-list

Don't be sad if you could not Merge K sorted linked lists. This is part of the learning process.

Please have a look at the algorithm, and then again, you must give it a try.

### PseudoCode

**Algorithm**

___________________________________________________________________

**procedure** mergeKLists(Node* arr[], int last):

___________________________________________________________________

1. result=0

Node *prev = NULL, *curr = head;

2. Loop till last!=0:

3. int i = 0, j = last;

4. while (i < j):

5. arr[i] = SortedMerge(arr[i], arr[j])

6. i++, j--;

7. if (i >= j) last = j;

8. End loop and return result

return arr[0]

**end procedure**

**___________________________________________________________________**

### Implementation in C++

### C++

`// Merge K sorted linked lists`

#include <bits/stdc++.h>

using namespace std;

// Structure of a Linked List node

struct Node {

int data;

Node* next;

};

// Function to print nodes

void printList(Node* node)

{

while (node != NULL) {

printf("%d ", node->data);

node = node->next;

}

}

//Taking two lists sorted in ascending order and merging their nodes to make one extensive sorted list.

Node* SortedMerge(Node* a, Node* b)

{

Node* result = NULL;

//Base case to end search

if (a == NULL)

return (b);

else if (b == NULL)

return (a);

// Choose either a or b, and start recursion

if (a->data <= b->data) {

result = a;

result->next = SortedMerge(a->next, b);

}

else {

result = b;

result->next = SortedMerge(a, b->next);

}

return result;

}

// Primary function that gives sorted output.

Node* mergeKLists(Node* arr[], int last)

{

// repeat until only one list is left

while (last != 0) {

int i = 0, j = last;

while (i < j) {

// merge List i with List j and store it in List i

arr[i] = SortedMerge(arr[i], arr[j]);

// consider next pair

i++, j--;

// If all pairs are merged, update last

if (i >= j)

last = j;

}

}

return arr[0];

}

// function to create a new node.

Node* newNode(int data)

{

struct Node* temp = new Node;

temp->data = data;

temp->next = NULL;

return temp;

}

int main()

{

//k is for Number of linked lists and n for Number of elements in each list

int k = 3;

int n = 4;

// an array of pointers storing the head nodes of the linked lists

Node* arr[k];

arr[0] = newNode(1);

arr[0]->next = newNode(3);

arr[0]->next->next = newNode(5);

arr[0]->next->next->next = newNode(7);

arr[1] = newNode(2);

arr[1]->next = newNode(4);

arr[1]->next->next = newNode(6);

arr[1]->next->next->next = newNode(8);

arr[2] = newNode(0);

arr[2]->next = newNode(9);

arr[2]->next->next = newNode(10);

arr[2]->next->next->next = newNode(11);

// Merge all lists

Node* head = mergeKLists(arr, k - 1);

printList(head);

return 0;

}

**Output:**

```
Input: {1 3 5 7}, {2 4 6 8}, {0 9 10 11}
Output: 0 1 2 3 4 5 6 7 8 9 10 11
```

#### Complexity Analysis

**Time Complexity:** **O(n*log k).**

**Analysing Time Complexity:**

The worst Time taken to sort is O(n*log k)

**Space complexity**: O(n)

## Frequently Asked Questions

### What is the difference between an array and a linked list?

The array consists of a similar data type, which is not necessary in the case of a linked list. The array is stored in a contiguous memory location, whereas a linked list can be stored randomly.

### What do you mean by heapify?

It is the conversion process into the heap data structure, say min-heap or max-heap. Here it is used for sorting the elements in increasing order.

### What is merge sort on sorted lists?

Merge sort is a divide-and-conquer sorting algorithm with a time complexity of O(nlogn). You can merge any number of sorted linked lists using the merge function of the merge sort algorithm in linear time complexity.

## Conclusion

This article taught us how to **Merge K sorted linked lists**. We discussed its implementation using illustrations, pseudocode, and then proper code.

We hope you could take away critical techniques like analyzing problems by walking over the execution of the examples and finding out the recursive pattern followed in most linked list problems.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

To study more about Linked Lists, refer to __Applications Of Linked Lists__.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.