Last Updated on June 15, 2022 by Ria Pathak

### Introduction

The linked list is one of the most important concepts to know while preparing for interviews. Having a good grasp of a linked list can be a huge plus point in coding interviews.

### Problem Statement

In this problem, we will be given **K** sorted linked lists. We need to merge all lists such that the newly created list is also in sorted order.

### Problem Statement Understanding

The problem statement is quite straightforward, we will be given **K** linked lists that are sorted in nature, and then we need to form a linked list using the nodes of all the given linked lists such that the newly formed list is sorted in order.

Let’s try to understand the problem with the help of examples:

If the sorted lists given to us are 2→3→5→NULL, 1→4→8→NULL, and 6→7→9→NULL.

- According to the problem statement, we need to merge all these given linked lists into a single linked list in such a way that after merging, the final linked list is sorted in nature.
- The list that we need to return must contain all the nodes of all three given lists in sorted order.
- So, after merging, the newly formed sorted list will be 1→2→3→4→5→6→7→8→9→NULL

Let’s take another example:

If the sorted lists given to us are 2→8→9→10→NULL, 11→13→17→NULL.

- In this case, after merging all the given lists, the final resultant sorted linked list will be 2→8→9→10→11→13→17→NULL

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

Before moving to the approach section, try to think about how you can approach this problem.

- If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

### Approach 1

- Initialize a
**result list**with the**first list**. - Traverse all
**K**lists one by one, starting from the second list, and merge them with the initialized**result list**using the merge two sorted list concepts. - At last, when we have traversed all the
**K**lists, our result list will be containing all the nodes of the**K**lists in sorted order. - Finally, we can return this
**result list**as our output.

**Note:** In case if you are not aware of how to merge two sorted linked lists, please check this article.

#### Some Important Observations

- Every time we add a sorted list into our result list, its size increases by
**N**(Complexity wise in the worst case we will take**N**as the size of the longest list out of all**K**lists). - So, when we add the second list, the complexity is
**2**.*N*N**. Then, on adding the third list, the complexity is**3 - Similarly, when we are adding the K
^{th}list, the complexity is **K*N**. - So, the total complexity is
**(2**.*N + 3*N + 4*N + …. + K*N) = N*(2+3+4+…+K)*K**, which is asymptotically equal to**(N^{2})

**Time Complexity:** **(N*K^{2})**, **N** is the number of nodes in the list, and **K** is the total number of lists
**Space Complexity:** O(1)

We can observe that if the number of lists given is quite large, then the above approach will result in TLE.

- So, we need to reduce the time complexity, which is possible if we use the divide and conquer technique.

### Approach 2

- In this approach, we merge the linked lists in pairs.
- In the first iteration, we will have
**K/2**pairs so; we will merge them using the merge two sorted lists concept. - Then after the first iteration, we will have
**K/2**lists, i.e.,**K/4**pairs of lists to merge. - After each iteration, the number of lists to be merged will reduce by half of their previous count.
- At last, we will be left with a single list which will contain all lists merged in sorted order.

Let’s move to the algorithm section.

### Algorithm

- Initialize a variable
**back**with the last array index (this array is containing the head of all the lists). - Run a while loop till
**back**is not equal to 0. - Inside while loop, we need to merge pairs so, initialize two variables, i.e.,
**i**with 0 and**j**with**back**. - Now, we need to run a while loop as long as
**i**is less than**j**. - Now merge i
^{th}and j^{th}list and store it as i^{th}element of the array. - Now, increment
**i**by one and decrement**j**by one. - If
**i**is greater than or equal to**j**, we need to update**back**, by**j**. - After execution of both the while loops, we need to return the first element of the array.

### Dry Run

### Code Implementation

#include#include #include struct Node { int data; struct Node* next; }; /* Function to print nodes in a given linked list */ void printList(struct Node* node) { while (node != NULL) { printf("%d ", node->data); node = node->next; } } // The main function that // takes an array of lists // arr[0..last] and generates // the sorted output struct Node* mergeKLists(struct Node* arr[], int last) { // Traverse form second list to last for (int i = 1; i <= last; i++) { while (true) { // head of both the lists, // 0 and ith list. struct Node *head_0 = arr[0], *head_i = arr[i]; // Break if list ended if (head_i == NULL) break; // Smaller than first element if (head_0->data >= head_i->data) { arr[i] = head_i->next; head_i->next = head_0; arr[0] = head_i; } else // Traverse the first list while (head_0->next != NULL) { // Smaller than next element if (head_0->next->data >= head_i->data) { arr[i] = head_i->next; head_i->next = head_0->next; head_0->next = head_i; break; } // go to next node head_0 = head_0->next; // if last node if (head_0->next == NULL) { arr[i] = head_i->next; head_i->next = NULL; head_0->next = head_i; head_0->next->next = NULL; break; } } } } return arr[0]; } // Utility function to create a new node. struct Node* newNode(int data) { struct Node *temp = (struct Node *) malloc(sizeof(struct Node)); temp->data = data; temp->next = NULL; return temp; } // Driver program to test // above functions int main() { // Number of linked lists int k = 3; // Number of elements in each list int n = 4; // an array of pointers storing the // head nodes of the linked lists struct Node* arr[k]; arr[0] = newNode(10); arr[0]->next = newNode(30); arr[0]->next->next = newNode(50); arr[0]->next->next->next = newNode(70); arr[1] = newNode(20); arr[1]->next = newNode(40); arr[1]->next->next = newNode(60); arr[1]->next->next->next = newNode(80); arr[2] = newNode(0); arr[2]->next = newNode(90); arr[2]->next->next = newNode(100); arr[2]->next->next->next = newNode(11); // Merge all lists struct Node* head = mergeKLists(arr, k - 1); printList(head); return 0; }

#includeusing namespace std; // class with constructor for a node of Linked list class Node { public: int data; Node* next; // constructor Node(int x){ data = x; next = NULL; } }; // This function prints data of the linked list void print(Node* head) { Node* curr = head; while (curr != NULL) { cout << curr->data << " -> "; curr = curr->next; } cout<<"NULL"; } // This function merges two sorted linked lists into one sorted // list Node *mergeTwoLists(Node *l1, Node *l2) { Node dummy(INT_MIN); Node *tail = &dummy; while (l1 && l2) { if (l1->data < l2->data) { tail->next = l1; l1 = l1->next; } else { tail->next = l2; l2 = l2->next; } tail = tail->next; } tail->next = l1 ? l1 : l2; return dummy.next; } // This function merges 'K' sorted lists into one sorted list Node* mergeKLists(Node* arr[], int back) { // run the while loop till 'back' is not equal to while (back != 0) { int i = 0, j = back; while (i < j) { // merge ith and jth list and store the list at // ith index of array arr[i] = mergeTwoLists(arr[i], arr[j]); // increment 'i' and decrement 'j' by one i++, j--; // update 'back' by 'j' once j is less than or // equal to 'i' if (i >= j) back = j; } } return arr[0]; } // main function int main() { Node * arr[3]; Node *head = new Node(2); head->next = new Node(3); head->next->next = new Node(5); Node *h2 = new Node(1); h2->next = new Node(4); h2->next->next = new Node(8); Node *h3 = new Node(6); h3->next = new Node(7); h3->next->next = new Node(9); arr[0] = head; arr[1] = h2; arr[2] = h3; cout<<"Final resultant merged linked list"<

class Node { int data; Node next; Node(int data) { this.data = data; } } class MergeK { public static Node SortedMerge(Node a, Node b) { Node result = null; /* Base cases */ if (a == null) return b; else if (b == null) return a; /* Pick either a or b, and recur */ if (a.data <= b.data) { result = a; result.next = SortedMerge(a.next, b); } else { result = b; result.next = SortedMerge(a, b.next); } return result; } // The main function that takes an array of lists // arr[0..last] and generates the sorted output public static Node mergeKLists(Node arr[], int last) { // repeat until only one list is left while (last != 0) { int i = 0, j = last; // (i, j) forms a pair while (i < j) { // merge List i with List j and store // merged list 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]; } public static void printList(Node node) { while (node != null) { System.out.print(node.data + " "); node = node.next; } } public static void main(String args[]) { int k = 3; // Number of linked lists int n = 4; // Number of elements in each list // an array of pointers storing the head nodes // of the linked lists Node arr[] = new Node[k]; arr[0] = new Node(1); arr[0].next = new Node(3); arr[0].next.next = new Node(5); arr[0].next.next.next = new Node(7); arr[1] = new Node(2); arr[1].next = new Node(4); arr[1].next.next = new Node(6); arr[1].next.next.next = new Node(8); arr[2] = new Node(0); arr[2].next = new Node(9); arr[2].next.next = new Node(10); arr[2].next.next.next = new Node(11); // Merge all lists Node head = mergeKLists(arr, k - 1); printList(head); } }

# A Linked List node class Node: def __init__(self, x): self.data = x self.next = None # Function to print nodes in # a given linked list def printList(node): while (node != None): print(node.data, end = " ") node = node.next def mergeKLists(arr, last): for i in range(1, last + 1): while (True): head_0 = arr[0] head_i = arr[i] if (head_i == None): break if (head_0.data >= head_i.data): arr[i] = head_i.next head_i.next = head_0 arr[0] = head_i else: while (head_0.next != None): if (head_0.next.data >= head_i.data): arr[i] = head_i.next head_i.next = head_0.next head_0.next = head_i break head_0 = head_0.next if (head_0.next == None): arr[i] = head_i.next head_i.next = None head_0.next = head_i head_0.next.next = None break return arr[0] if __name__ == '__main__': k = 3 arr = [None for i in range(k)] arr[0] = Node(2) arr[0].next = Node(3) arr[0].next.next = Node(5) arr[1] = Node(1) arr[1].next = Node(4) arr[1].next.next = Node(8) arr[2] = Node(6) arr[2].next = Node(7) arr[2].next.next = Node(9) head = mergeKLists(arr, k - 1) print("Final resultant merged linked list") printList(head)

#### Output

Final resultant merged linked list

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> NULL

**Time Complexity:** O(NKlog(K)), **N** is the number of nodes in the list, and **K** is the total number of lists

[forminator_quiz id=”5128″]

There is also a min heap based solution to this problem, to check out the heap based solution please visit [Merge K sorted linked lists using min heap](Merge k sorted linked lists Set 2 Using Min Heap).

So, in this blog, we have tried to explain how you can merge **K** sorted linked lists in the most optimal way. If you want to practice more questions on linked lists, feel free to solve them at Prepbytes Linked List.