1.
Introduction
2.
Problem Statement
3.
Sample Example
4.
Naive Approach
5.
Optimised Approach
5.1.
PseudoCode
5.2.
Implementation in C++
5.3.
C++
5.3.1.
Complexity Analysis
6.
6.1.
What is the difference between an array and a linked list?
6.2.
What do you mean by heapify?
6.3.
What is merge sort on sorted lists?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Merge K Sorted Linked Lists

Urwashi Priya
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

## Introduction

In this blog, we will discuss a linked list problem that has been asked frequently in Interviews.

The problem is to Merge K sorted linked lists.

I am starting with what is a linked list.

It is an ordered set of elements, each holding data and a link containing the address to the next element.

We are now coming to the question.

Also, see Data Structures

## Problem Statement

We are given N elements each in K linked list, the elements given in each list are sorted, We bring a priority queue into the picture, and we are asked to Merge K sorted linked lists.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

Check if 1->next == NULL?

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

So priority queue now becomes 2,4,7.

Repeat this for 3.

Priority queue: 3,4,7

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.

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
___________________________________________________________________

• C++

### C++

``// Merge K sorted linked lists#include <bits/stdc++.h>using namespace std;// Structure of a Linked List nodestruct 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)

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