Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Last Updated on November 28, 2022 by Prepbytes

In this blog, we will discuss three different approaches to merge k sorted lists. Merging k sorted linked lists is a challenging topic and conquering it will make your data structures more efficient. Let’s discuss how to merge k sorted lists.

How to Merge K Sorted Linked List?

Yor are given K sorted linked lists. You have to merge K sorted linked lists into one sorted list. The size of the linked list maybe different.

See original problem statement here

Example:

``````Input:
[
list[1]:4−>6−>8−>10−>15
list[2]:1−>5−>9
list[3]:2−>3−>7−>11
]

Output:
1−>2−>3−>4−>5−>6−>7−>8−>9−>10−>11−>15``````

EXPLANATION:

Approach 1 To Merge K Sorted Lists`(Brute force):`

All the given lists are sorted, which means that the head of each list would be the smallest element in its chain. So we could extract the minimum from the k head nodes and append it to the result list.

`Time complexity To Merge K Sorted Lists In Brute Force approach`: `O(kN)` where `k` is the number of linked lists. Almost every selection of nodes in the final link costs `O(k)` `(k-1 times comparison)`.

`Space complexity To Merge K Sorted Lists`: `O(1)`.

Approach 2 To Merge K Sorted Lists:

The idea is to insert all the node values from all the `k` lists into an array. Sorting the array and creating a new linked list from the sorted array will give the required output.

Pseudo code:

``````     ListNode mergeKLists(ListNode[] lists, int k)
{
// x array to store all the values from lists
int x[]
for(i = 0 to k)
{
ListNode temp = lists[i]
while(temp is not null)
{
// append the value of temp to x
temp = temp.next
}
}
// sort all the values of x
sort(x)
for(i = 0 to x.size()) {
ListNode newVal(x[i])
temp.next = newVal
temp = temp.next
}
} ``````

`TIME COMPLEXITY To Merge K Sorted Lists`: O(NlogN).
`SPACE COMPLEXITY To Merge K Sorted Lists`: O(N),
where `N` is the total number of nodes

Approach 3 To Merge K Sorted Lists`(Heaps):`

1. Create a priority queue.
2. Insert the first node from all the lists into the priority queue.
3. Loop until the priority queue is not empty Extract the minimum node from the queue and add it to our result list.
4. Add the next node (if present) from the extracted node list.
5. Return the resultant list.

SOLUTIONS To Merge K Sorted Lists:

```#include
#include

struct Node {
int data;
struct Node* next;
};

/* Function to print nodes in
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}

/* Takes two lists sorted in increasing order, and merge
their nodes together to make one big sorted list. Below
function takes O(n) extra space for recursive calls,
*/
struct Node* SortedMerge(struct Node* a,struct Node* b)
{
struct 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
struct Node* mergeKLists(struct 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];
}

// 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()
{
int k = 3; // Number of linked lists
int n = 4; // Number of elements in each list

// an array of pointers storing the head nodes
struct 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
struct Node* head = mergeKLists(arr, k - 1);

return 0;
}
```
```#include
using namespace std;

struct Node {
int data;
struct Node* next;
};
struct compare {
bool operator()(struct Node* a, struct Node* b)
{
return a->data > b->data;
}
};

struct Node* mergeKSortedLists(struct Node* arr[], int k)
{
struct Node *head = NULL, *last;
priority_queue, compare> pq;
for (int i = 0; i < k; i++)
if (arr[i] != NULL)
pq.push(arr[i]);

while (!pq.empty()) {
struct Node* top = pq.top();
pq.pop();
if (top->next != NULL)
pq.push(top->next);
last = top;
}

else {
last->next = top;
last = top;
}
}
}
{
cout << head->data << " ";
}
}
struct Node* newNode(int data)
{
struct Node* new_node = new Node();
new_node->data = data;
new_node->next = NULL;

return new_node;
}
int main()
{
int k;cin>>k;
Node* arr[k];
for(int i=0;i>n;
int x;cin>>x;
arr[i]=newNode(x);
for(int j=1;j>x;
}
}
struct Node* head = mergeKSortedLists(arr, k);

return 0;
}
```
```import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.*;
class Node {
int data;
Node next;

public Node(int data) {
this.data = data;
this.next = null;
}
}

public class Main
{
public static void printList(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
public static Node mergeKLists(Node[] list, int k)
{
PriorityQueue pq;
pq = new PriorityQueue(Comparator.comparingInt(a -> ((Node) a).data));
Node head = null, last = null;
while (!pq.isEmpty())
{
Node min = pq.poll();
} else {
last.next = min;
last = min;
}
if (min.next != null) {
}
}
}

public static void main(String[] s) {
Scanner sc = new Scanner(System.in);
int k= sc.nextInt();
Node[] list = new Node[k];
for(int i=0;i

```
```import heapq
from heapq import heappop, heappush
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next

def __lt__(self, other):
return self.data < other.data

def printList(node):
while node:
print(node.data, end=' —> ')
node = node.next

print('None')

def mergeKLists(lists):

pq = [x for x in lists]
heapq.heapify(pq)

while pq:

min = heappop(pq)

last = min
else:
last.next = min
last = min

if min.next:
heappush(pq, min.next)

if __name__ == '__main__':

k = 3

lists = [None] * k

lists[0] = Node(4)
lists[0].next = Node(6)
lists[0].next.next = Node(8)
lists[0].next.next.next = Node(10)
lists[0].next.next.next.next = Node(15)

lists[1] = Node(1)
lists[1].next = Node(5)
lists[1].next.next = Node(9)

lists[2] = Node(2)
lists[2].next = Node(3)
lists[2].next.next = Node(7)
lists[2].next.next.next = Node(11)

```

This blog discusses different approaches for figuring out how to merge k sorted lists. Every approach is important as knowing that will help you to understand the advantages and disadvantages of that approach. Targeting topics of data structures like Linked lists, Heaps, Priority queue will definitely help you to grab your dream job. For Practicing more questions, you can check out MYCODE | Competitive Programming.

FAQ

1. How do I merge two sorted lists?
Merge two sorted linked lists using Dummy Nodes:

• First, make a dummy node for the new merged linked list.
• Now make two pointers, one will point to list1 and another will point to list2.
• Now traverse the lists till one of them gets exhausted.

2. Which companies have recently asked how to merge k sorted lists?
Samsung, SquadStack, Amazon, and Josh Technologies in their recent technical interviews have asked this question.