Table of contents
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.
Frequently Asked Questions
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

Author Urwashi Priya
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

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

Merge K Sorted Linked Lists

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.

To know more about the linked list, refer here.

Linked-List

sorted linked lists

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.

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.

 resultant linked list

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

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;
}
You can also try this code with Online C++ Compiler
Run Code

 

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.

Live masterclass