Posted on by Kalkicode

The problem at hand involves merging K sorted linked lists into a single sorted linked list. Each linked list is already sorted in ascending order. The task is to efficiently merge all these sorted lists into one, while preserving the sorted order. This problem often appears in scenarios like merging sorted arrays, implementing priority queues, or combining data from multiple sources in a sorted manner.

Problem Statement

Given K sorted linked lists, the problem is to merge them into a single linked list that maintains the sorted order. For instance, if we have K = 4 sorted linked lists:

List 1: 1 → 3 → 14 → 19
List 2: 0 → 0 → 2 → 4
List 3: -3 → 5 → 8 → 12 → 12 → 15 → 17
List 4: 8 → 15 → 44

The merged linked list should be:

-3 → 0 → 0 → 1 → 2 → 3 → 4 → 5 → 8 → 8 → 12 → 12 → 14 → 15 → 15 → 17 → 19 → 44

Idea to Solve

The idea to solve this problem is to use a technique similar to merge sort. We will repeatedly select the smallest element among the heads of all K linked lists and add it to the merged list. As we add an element to the merged list, we move the pointer of the respective linked list to its next node. This way, we progress through all the linked lists, always selecting the smallest available element to add to the merged list.

Pseudocode

Here's the pseudocode that outlines the algorithm to merge K sorted linked lists:

function mergeKSortedLists(lists):
Create a min-heap data structure to track the smallest element from each list
Create a dummy node and a pointer to it as the merged linked list's head
Insert the first element of each list into the min-heap

while min-heap is not empty:
Pop the smallest element from the min-heap
Add the popped element to the merged list
Move the corresponding list pointer to its next element
If the list is not empty, insert its next element into the min-heap

Algorithm Explanation

• We start by creating a min-heap to keep track of the smallest element from each list. Min-heap ensures that the smallest element can be efficiently popped.
• We create a dummy node and a pointer that will traverse the merged linked list.
• We insert the first element of each list into the min-heap.
• The algorithm iterates as long as the min-heap is not empty. In each iteration:
• We pop the smallest element from the min-heap.
• We add the popped element to the merged linked list using the pointer.
• We move the corresponding list pointer to its next element.
• If the list is not empty, we insert its next element into the min-heap to maintain the next smallest element.
• The algorithm continues this process until all elements have been merged into the final linked list.

Code Solution

//C Program
#include <stdio.h>

#include <stdlib.h> //for malloc function

struct Node
{
int data;
struct Node *next;
struct Node *prev;
};
//insert Node element of end of linked list
void insert(struct Node **head, int value)
{
//Create a dynamic node
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
if (node == NULL)
{
printf("Memory overflow\n");
}
else
{
//Set data value
node->data = value;
node->next = NULL;
node->prev = NULL;
{
}
else
{
//Find last node
while (temp != NULL && temp->next != NULL)
{
temp = temp->next;
}
//Add new node to last position
temp->next = node;
node->prev = temp;
}
}
}
//This function are displayed group of given linked lists
void print_list(struct Node *list[], int size)
{
if (size <= 0)
{
}
else
{
struct Node *temp = NULL;
for (int i = 0; i < size; i++)
{
temp = list[i];
while (temp != NULL)
{
//print node value
printf("%3d", temp->data);
temp = temp->next;
}
printf("\n");
}
printf("\n");
}
}
// This function arrange the linked list node in sorted order
// by using swapping node operation
{
int temp = 0;
{
}
}
//This function is sorted given linked list elements
void sort(struct Node *auxiliary[], int size)
{
int position = -1, source = -1, temp = 0;
//Get first node position of given linked lists
for (int i = 0; i < size && position == -1; ++i)
{
if (auxiliary[i] != NULL)
{
//When list i are not null
position = i;
}
}
if (position != -1)
{
//When need to sort list elements
source = -1;
temp = position;
//Find smallest node location of lists
for (int i = position + 1; i < size; ++i)
{
if (auxiliary[i] != NULL && auxiliary[i]->data < auxiliary[temp]->data)
{
source = i;
temp = i;
}
}
if (source != -1)
{
temp = auxiliary[position]->data;
//Swap node value
auxiliary[position]->data = auxiliary[source]->data;
auxiliary[source]->data = temp;
//after swap arrange second list elements in sorted order.
update_record(auxiliary[source]);
}
//visit next node
auxiliary[position] = (auxiliary[position])->next;
//Recursive executed, until when given list need sorting operation
sort(auxiliary, size);
}
}
//This function are handle the request to sort elements in given linked lists
//Assuming that given linked list contains sorted elements
void *sort_list(struct Node *list[], int size)
{
//This is used to store first node of each linked list
struct Node *auxiliary[size];
int i = 0;
//This loop are obtain the first node of each linked list
for (i = 0; i < size; i++)
{
//Get first node of lists
auxiliary[i] = list[i];
}
sort(auxiliary, size);
i = 0;
//This loop are combining linked lists nodes
while (i < size - 1)
{
{
i++;
//This is not important but given multiple lists and each list are share their nudes to other
list[i] = list[0];
}
}
}
//This function are display given linked list elements
{
{
//print node value
}
}
int main()
{
struct Node *list[4] = {
NULL
};
insert( & list[0], 1);
insert( & list[0], 3);
insert( & list[0], 14);
insert( & list[0], 19);
insert( & list[1], 0);
insert( & list[1], 0);
insert( & list[1], 2);
insert( & list[1], 4);
insert( & list[2], -3);
insert( & list[2], 5);
insert( & list[2], 8);
insert( & list[2], 12);
insert( & list[2], 12);
insert( & list[2], 15);
insert( & list[2], 17);
insert( & list[3], 8);
insert( & list[3], 15);
insert( & list[3], 44);
int k = sizeof(list) / sizeof(list[0]);
//Before
print_list(list, k);
sort_list(list, k);
printf(" After Sort \n ");
//After sort display the linked list elements
display(list[0]);
return 0;
}

Output

1  3 14 19
0  0  2  4
-3  5  8 12 12 15 17
8 15 44

After Sort
-3  0  0  1  2  3  4  5  8  8 12 12 14 15 15 17 19 44
//Java Program

class Node
{
public int data;
public Node next;
public Node prev;
public Node(int data)
{
this.data = data;
this.next = null;
this.prev = null;
}
}
class DoublyList
{
//insert Node element of end of linked list
public Node insert(Node head, int value)
{
//Create a dynamic node
Node node = new Node(value);
if (node == null)
{
System.out.print("Memory overflow\n");
}
else
{
{
return node;
}
else
{
//Find last node
while (temp != null && temp.next != null)
{
temp = temp.next;
}
//Add new node to last position
temp.next = node;
node.prev = temp;
}
}
}
//This function are displayed group of given linked lists
public void print_list(Node[] lists, int size)
{
if (size <= 0)
{
}
else
{
Node temp = null;
for (int i = 0; i < size; i++)
{
temp = lists[i];
while (temp != null)
{
System.out.print(" " + temp.data + "");
temp = temp.next;
}
System.out.print("\n");
}
System.out.print("\n");
}
}
// This function arrange the linked list node in sorted order
// by using swapping node operation
{
int temp = 0;
{
}
}
//This function is sorted given linked list elements
public void sort(Node[] auxiliary, int size)
{
int position = -1, source = -1, temp = 0;
//Get first node position of given linked lists
for (int i = 0; i < size && position == -1; ++i)
{
if (auxiliary[i] != null)
{
//When list i are not null
position = i;
}
}
if (position != -1)
{
//When need to sort list elements
source = -1;
temp = position;
//Find smallest node location of lists
for (int i = position + 1; i < size; ++i)
{
if (auxiliary[i] != null && auxiliary[i].data < auxiliary[temp].data)
{
source = i;
temp = i;
}
}
if (source != -1)
{
temp = auxiliary[position].data;
//Swap node value
auxiliary[position].data = auxiliary[source].data;
auxiliary[source].data = temp;
//after swap arrange second list elements in sorted order.
update_record(auxiliary[source]);
}
//visit next node
auxiliary[position] = (auxiliary[position]).next;
//Recursive executed, until when given list need sorting operation
sort(auxiliary, size);
}
}
//This function are handle the request to sort elements in given linked lists
//Assuming that given linked list contains sorted elements
public void sort_list(Node[] lists, int size)
{
//This is used to store first node of each linked list
Node[] auxiliary = new Node[size];
int i = 0;
//This loop are obtain the first node of each linked list
for (i = 0; i < size; i++)
{
//Get first node of lists
auxiliary[i] = lists[i];
}
sort(auxiliary, size);
i = 0;
//This loop are combining linked lists nodes
while (i < size - 1)
{
{
i++;
//This is not important but given multiple lists and each list are share their nudes to other
lists[i] = lists[0];
}
}
}
//This function are display given linked list elements
{
{
System.out.print(" " + head.data + " ");
}
}

public static void main(String[] args)
{
DoublyList obj = new DoublyList();
int k = 4 ;
Node[] lists = new Node[4];

for(int i=0;i<k;i++)
{
lists[i] = null;
}
lists[0]=obj.insert(lists[0], 1);
obj.insert(lists[0], 3);
obj.insert(lists[0], 14);
obj.insert(lists[0], 19);
lists[1]=obj.insert(lists[1], 0);
obj.insert(lists[1], 0);
obj.insert(lists[1], 2);
obj.insert(lists[1], 4);
lists[2]=obj.insert(lists[2], -3);
obj.insert(lists[2], 5);
obj.insert(lists[2], 8);
obj.insert(lists[2], 12);
obj.insert(lists[2], 12);
obj.insert(lists[2], 15);
obj.insert(lists[2], 17);
lists[3]=obj.insert(lists[3], 8);
obj.insert(lists[3], 15);
obj.insert(lists[3], 44);

obj.print_list(lists, k);
obj.sort_list(lists, k);
System.out.print(" After Sort \n ");
//After sort display the linked list elements
obj.display(lists[0]);
}
}

Output

1 3 14 19
0 0 2 4
-3 5 8 12 12 15 17
8 15 44

After Sort
-3  0  0  1  2  3  4  5  8  8  12  12  14  15  15  17  19  44
#include <iostream>

using namespace std;

//C++ Program
class Node
{
public: int data;
Node * next;
Node * prev;
Node()
{
this->data = 0;
this->next = NULL;
this->prev = NULL;
}
Node(int data)
{
this->data = data;
this->next = NULL;
this->prev = NULL;
}
};
class DoublyList
{
public:
//insert Node element of end of linked list
Node * insert(Node * head, int value)
{
//Create a dynamic node
Node * node = new Node(value);
if (node == NULL)
{
cout << "Memory overflow\n";
}
else
{
{
return node;
}
else
{
//Find last node
while (temp != NULL && temp->next != NULL)
{
temp = temp->next;
}
//Add new node to last position
temp->next = node;
node->prev = temp;
}
}
}
//This function are displayed group of given linked lists
void print_list(Node* lists[], int size)
{
if (size <= 0)
{
}
else
{
Node * temp = NULL;
for (int i = 0; i < size; i++)
{
temp = lists[i];
while (temp != NULL)
{
cout << " " << temp->data << "";
temp = temp->next;
}
cout << "\n";
}
cout << "\n";
}
}
// This function arrange the linked list node in sorted order
// by using swapping node operation
{
int temp = 0;
{
}
}
//This function is sorted given linked list elements
void sort(Node *auxiliary[], int size)
{
int position = -1, source = -1, temp = 0;
//Get first node position of given linked lists
for (int i = 0; i < size && position == -1; ++i)
{
if (auxiliary[i] != NULL)
{
//When list i are not null
position = i;
}
}
if (position != -1)
{
//When need to sort list elements
source = -1;
temp = position;
//Find smallest node location of lists
for (int i = position + 1; i < size; ++i)
{
if (auxiliary[i] != NULL && auxiliary[i]->data < auxiliary[temp]->data)
{
source = i;
temp = i;
}
}
if (source != -1)
{
temp = auxiliary[position]->data;
//Swap node value
auxiliary[position]->data = auxiliary[source]->data;
auxiliary[source]->data = temp;
//after swap arrange second list elements in sorted order.
this->update_record(auxiliary[source]);
}
//visit next node
auxiliary[position] = auxiliary[position]->next;
//Recursive executed, until when given list need sorting operation
this->sort(auxiliary, size);
}
}
//This function are handle the request to sort elements in given linked lists
//Assuming that given linked list contains sorted elements
void sort_list(Node* lists[], int size)
{
Node * auxiliary[size];
int i = 0;
//This loop are obtain the first node of each linked list
for (i = 0; i < size; i++)
{
//Get first node of lists
auxiliary[i] = lists[i];
}
this->sort(auxiliary, size);
i = 0;
//This loop are combining linked lists nodes
while (i < size - 1)
{
{
i++;
//This is not important but given multiple lists and each list are share their nudes to other
lists[i] = lists[0];
}
}
}
//This function are display given linked list elements
{
{
cout << " " << head->data << " ";
}
}
};
int main()
{
DoublyList obj = DoublyList();
int k = 4;
Node * lists[4];
for (int i = 0; i < k; i++)
{
lists[i] = NULL;
}
lists[0] = obj.insert(lists[0], 1);
obj.insert(lists[0], 3);
obj.insert(lists[0], 14);
obj.insert(lists[0], 19);
lists[1] = obj.insert(lists[1], 0);
obj.insert(lists[1], 0);
obj.insert(lists[1], 2);
obj.insert(lists[1], 4);
lists[2] = obj.insert(lists[2], -3);
obj.insert(lists[2], 5);
obj.insert(lists[2], 8);
obj.insert(lists[2], 12);
obj.insert(lists[2], 12);
obj.insert(lists[2], 15);
obj.insert(lists[2], 17);
lists[3] = obj.insert(lists[3], 8);
obj.insert(lists[3], 15);
obj.insert(lists[3], 44);
obj.print_list(lists, k);
obj.sort_list(lists, k);
cout << " After Sort \n ";
//After sort display the linked list elements
obj.display(lists[0]);
return 0;
}

Output

1 3 14 19
0 0 2 4
-3 5 8 12 12 15 17
8 15 44

After Sort
-3  0  0  1  2  3  4  5  8  8  12  12  14  15  15  17  19  44
//Include namespace system
using System;
//C# Program
public class Node
{
public int data;
public Node next;
public Node prev;
public Node(int data)
{
this.data = data;
this.next = null;
this.prev = null;
}
}
public class DoublyList
{
//insert Node element of end of linked list
public Node insert(Node head, int value)
{
//Create a dynamic node
Node node = new Node(value);
if (node == null)
{
Console.Write("Memory overflow\n");
}
else
{
{
return node;
}
else
{
//Find last node
while (temp != null && temp.next != null)
{
temp = temp.next;
}
//Add new node to last position
temp.next = node;
node.prev = temp;
}
}
}
//This function are displayed group of given linked lists
public void print_list(Node[] lists, int size)
{
if (size <= 0)
{
}
else
{
Node temp = null;
for (int i = 0; i < size; i++)
{
temp = lists[i];
while (temp != null)
{
Console.Write(" " + temp.data + "");
temp = temp.next;
}
Console.Write("\n");
}
Console.Write("\n");
}
}
// This function arrange the linked list node in sorted order
// by using swapping node operation
{
int temp = 0;
{
}
}
//This function is sorted given linked list elements
public void sort(Node[] auxiliary, int size)
{
int position = -1, source = -1, temp = 0;
//Get first node position of given linked lists
for (int i = 0; i < size && position == -1; ++i)
{
if (auxiliary[i] != null)
{
//When list i are not null
position = i;
}
}
if (position != -1)
{
//When need to sort list elements
source = -1;
temp = position;
//Find smallest node location of lists
for (int i = position + 1; i < size; ++i)
{
if (auxiliary[i] != null && auxiliary[i].data < auxiliary[temp].data)
{
source = i;
temp = i;
}
}
if (source != -1)
{
temp = auxiliary[position].data;
//Swap node value
auxiliary[position].data = auxiliary[source].data;
auxiliary[source].data = temp;
//after swap arrange second list elements in sorted order.
update_record(auxiliary[source]);
}
//visit next node
auxiliary[position] = (auxiliary[position]).next;
//Recursive executed, until when given list need sorting operation
sort(auxiliary, size);
}
}
//This function are handle the request to sort elements in given linked lists
//Assuming that given linked list contains sorted elements
public void sort_list(Node[] lists, int size)
{
Node[] auxiliary = new Node[size];
int i = 0;
//This loop are obtain the first node of each linked list
for (i = 0; i < size; i++)
{
//Get first node of lists
auxiliary[i] = lists[i];
}
sort(auxiliary, size);
i = 0;
//This loop are combining linked lists nodes
while (i < size - 1)
{
{
i++;
//This is not important but given multiple lists and each list are share their nudes to other
lists[i] = lists[0];
}
}
}
//This function are display given linked list elements
{
{
Console.Write(" " + head.data + " ");
}
}
public static void Main(String[] args)
{
DoublyList obj = new DoublyList();
int k = 4;
Node[] lists = new Node[4];
for (int i = 0; i < k; i++)
{
lists[i] = null;
}
lists[0] = obj.insert(lists[0], 1);
obj.insert(lists[0], 3);
obj.insert(lists[0], 14);
obj.insert(lists[0], 19);
lists[1] = obj.insert(lists[1], 0);
obj.insert(lists[1], 0);
obj.insert(lists[1], 2);
obj.insert(lists[1], 4);
lists[2] = obj.insert(lists[2], -3);
obj.insert(lists[2], 5);
obj.insert(lists[2], 8);
obj.insert(lists[2], 12);
obj.insert(lists[2], 12);
obj.insert(lists[2], 15);
obj.insert(lists[2], 17);
lists[3] = obj.insert(lists[3], 8);
obj.insert(lists[3], 15);
obj.insert(lists[3], 44);
obj.print_list(lists, k);
obj.sort_list(lists, k);
Console.Write(" After Sort \n ");
//After sort display the linked list elements
obj.display(lists[0]);
}
}

Output

1 3 14 19
0 0 2 4
-3 5 8 12 12 15 17
8 15 44

After Sort
-3  0  0  1  2  3  4  5  8  8  12  12  14  15  15  17  19  44
<?php
//Php Program
class Node
{
public \$data;
public \$next;
public \$prev;

function __construct(\$data)
{
\$this->data = \$data;
\$this->next = null;
\$this->prev = null;
}
}
class DoublyList
{
//insert Node element of end of linked list
{
//Create a dynamic node
\$node = new Node(\$value);
if (\$node == null)
{
echo "Memory overflow\n";
}
else
{
{
return \$node;
}
else
{
//Find last node
while (\$temp != null && \$temp->next != null)
{
\$temp = \$temp->next;
}
//Add new node to last position
\$temp->next = \$node;
\$node->prev = \$temp;
}
}
}
//This function are displayed group of given linked lists
public	function print_list( & \$lists, \$size)
{
if (\$size <= 0)
{
}
else
{
\$temp = null;
for (\$i = 0; \$i < \$size; \$i++)
{
\$temp = \$lists[\$i];
while (\$temp != null)
{
echo " ". \$temp->data ."";
\$temp = \$temp->next;
}
echo "\n";
}
echo "\n";
}
}
// This function arrange the linked list node in sorted order
// by using swapping node operation
{
\$temp = 0;
{
}
}
//This function is sorted given linked list elements
public	function sort( & \$auxiliary, \$size)
{
\$position = -1;
\$source = -1;
\$temp = 0;
//Get first node position of given linked lists
for (\$i = 0; \$i < \$size && \$position == -1; ++\$i)
{
if (\$auxiliary[\$i] != null)
{
//When list i are not null
\$position = \$i;
}
}
if (\$position != -1)
{
//When need to sort list elements
\$source = -1;
\$temp = \$position;
//Find smallest node location of lists
for (\$i = \$position + 1; \$i < \$size; ++\$i)
{
if (\$auxiliary[\$i] != null && \$auxiliary[\$i]->data < \$auxiliary[\$temp]->data)
{
\$source = \$i;
\$temp = \$i;
}
}
if (\$source != -1)
{
\$temp = \$auxiliary[\$position]->data;
//Swap node value
\$auxiliary[\$position]->data = \$auxiliary[\$source]->data;
\$auxiliary[\$source]->data = \$temp;
//after swap arrange second list elements in sorted order.
\$this->update_record(\$auxiliary[\$source]);
}
//visit next node
\$auxiliary[\$position] = \$auxiliary[\$position]->next;
//Recursive executed, until when given list need sorting operation
\$this->sort(\$auxiliary, \$size);
}
}
//This function are handle the request to sort elements in given linked lists
//Assuming that given linked list contains sorted elements
public	function sort_list( & \$lists, \$size)
{
//This is used to store first node of each linked list
\$auxiliary = array_fill(0, \$size, null);
\$i = 0;
//This loop are obtain the first node of each linked list
for (\$i = 0; \$i < \$size; \$i++)
{
//Get first node of lists
\$auxiliary[\$i] = \$lists[\$i];
}
\$this->sort(\$auxiliary, \$size);
\$i = 0;
//This loop are combining linked lists nodes
while (\$i < \$size - 1)
{
{
\$i++;
//This is not important but given multiple lists and each list are share their nudes to other
\$lists[\$i] = \$lists[0];
}
}
}
//This function are display given linked list elements
{
{
echo " ". \$head->data ." ";
}
}
}

function main()
{
\$obj = new DoublyList();
\$k = 4;
\$lists = array_fill(0, 4, null);
for (\$i = 0; \$i < \$k; \$i++)
{
\$lists[\$i] = null;
}
\$lists[0] = \$obj->insert(\$lists[0], 1);
\$obj->insert(\$lists[0], 3);
\$obj->insert(\$lists[0], 14);
\$obj->insert(\$lists[0], 19);
\$lists[1] = \$obj->insert(\$lists[1], 0);
\$obj->insert(\$lists[1], 0);
\$obj->insert(\$lists[1], 2);
\$obj->insert(\$lists[1], 4);
\$lists[2] = \$obj->insert(\$lists[2], -3);
\$obj->insert(\$lists[2], 5);
\$obj->insert(\$lists[2], 8);
\$obj->insert(\$lists[2], 12);
\$obj->insert(\$lists[2], 12);
\$obj->insert(\$lists[2], 15);
\$obj->insert(\$lists[2], 17);
\$lists[3] = \$obj->insert(\$lists[3], 8);
\$obj->insert(\$lists[3], 15);
\$obj->insert(\$lists[3], 44);
\$obj->print_list(\$lists, \$k);
\$obj->sort_list(\$lists, \$k);
echo " After Sort \n ";
//After sort display the linked list elements
\$obj->display(\$lists[0]);
}
main();

Output

1 3 14 19
0 0 2 4
-3 5 8 12 12 15 17
8 15 44

After Sort
-3  0  0  1  2  3  4  5  8  8  12  12  14  15  15  17  19  44
//Node Js Program
class Node
{
constructor(data)
{
this.data = data;
this.next = null;
this.prev = null;
}
}
class DoublyList
{
//insert Node element of end of linked list
{
//Create a dynamic node
var node = new Node(value);
if (node == null)
{
process.stdout.write("Memory overflow\n");
}
else
{
{
return node;
}
else
{
//Find last node
while (temp != null && temp.next != null)
{
temp = temp.next;
}
//Add new node to last position
temp.next = node;
node.prev = temp;
}
}
}
//This function are displayed group of given linked lists
print_list(lists, size)
{
if (size <= 0)
{
}
else
{
var temp = null;
for (var i = 0; i < size; i++)
{
temp = lists[i];
while (temp != null)
{
process.stdout.write(" " + temp.data + "");
temp = temp.next;
}
process.stdout.write("\n");
}
process.stdout.write("\n");
}
}
// This function arrange the linked list node in sorted order
// by using swapping node operation
{
var temp = 0;
{
}
}
//This function is sorted given linked list elements
sort(auxiliary, size)
{
var position = -1;
var source = -1;
var temp = 0;
//Get first node position of given linked lists
for (var i = 0; i < size && position == -1; ++i)
{
if (auxiliary[i] != null)
{
//When list i are not null
position = i;
}
}
if (position != -1)
{
//When need to sort list elements
source = -1;
temp = position;
//Find smallest node location of lists
for (var i = position + 1; i < size; ++i)
{
if (auxiliary[i] != null && auxiliary[i].data < auxiliary[temp].data)
{
source = i;
temp = i;
}
}
if (source != -1)
{
temp = auxiliary[position].data;
//Swap node value
auxiliary[position].data = auxiliary[source].data;
auxiliary[source].data = temp;
//after swap arrange second list elements in sorted order.
this.update_record(auxiliary[source]);
}
//visit next node
auxiliary[position] = auxiliary[position].next;
//Recursive executed, until when given list need sorting operation
this.sort(auxiliary, size);
}
}
//This function are handle the request to sort elements in given linked lists
//Assuming that given linked list contains sorted elements
sort_list(lists, size)
{
//This is used to store first node of each linked list
var auxiliary = Array(size).fill(null);
var i = 0;
//This loop are obtain the first node of each linked list
for (i = 0; i < size; i++)
{
//Get first node of lists
auxiliary[i] = lists[i];
}
this.sort(auxiliary, size);
i = 0;
//This loop are combining linked lists nodes
while (i < size - 1)
{
{
i++;
//This is not important but given multiple lists and each list are share their nudes to other
lists[i] = lists[0];
}
}
}
//This function are display given linked list elements
{
{
process.stdout.write(" " + head.data + " ");
}
}
}

function main()
{
var obj = new DoublyList();
var k = 4;
var lists = Array(4).fill(null);
for (var i = 0; i < k; i++)
{
lists[i] = null;
}
lists[0] = obj.insert(lists[0], 1);
obj.insert(lists[0], 3);
obj.insert(lists[0], 14);
obj.insert(lists[0], 19);
lists[1] = obj.insert(lists[1], 0);
obj.insert(lists[1], 0);
obj.insert(lists[1], 2);
obj.insert(lists[1], 4);
lists[2] = obj.insert(lists[2], -3);
obj.insert(lists[2], 5);
obj.insert(lists[2], 8);
obj.insert(lists[2], 12);
obj.insert(lists[2], 12);
obj.insert(lists[2], 15);
obj.insert(lists[2], 17);
lists[3] = obj.insert(lists[3], 8);
obj.insert(lists[3], 15);
obj.insert(lists[3], 44);
obj.print_list(lists, k);
obj.sort_list(lists, k);
process.stdout.write(" After Sort \n ");
//After sort display the linked list elements
obj.display(lists[0]);
}
main();

Output

1 3 14 19
0 0 2 4
-3 5 8 12 12 15 17
8 15 44

After Sort
-3  0  0  1  2  3  4  5  8  8  12  12  14  15  15  17  19  44
# Python 3 Program
# Merge K sorted linked lists
class Node :

def __init__(self, data) :
self.data = data
self.next = None
self.prev = None

class DoublyList :
# insert Node element of end of linked list
# Create a dynamic node
node = Node(value)
if (node == None) :
print("Memory overflow\n", end = "")
else :
return node
else :
# Find last node
while (temp != None and temp.next != None) :
temp = temp.next

# Add new node to last position
temp.next = node
node.prev = temp

# This function are displayed group of given linked lists
def print_list(self, lists, size) :
if (size <= 0) :
print("Empty linked list", end = "")
else :
temp = None
i = 0
while (i < size) :
temp = lists[i]
while (temp != None) :
print(" ", temp.data ,"", end = "")
temp = temp.next

print("\n", end = "")
i += 1

print("\n", end = "")

#  This function arrange the linked list node in sorted order
#  by using swapping node operation
temp = 0

# This function is sorted given linked list elements
def sort(self, auxiliary, size) :
position = -1
source = -1
temp = 0
# Get first node position of given linked lists
i = 0
while (i < size and position == -1) :
if (auxiliary[i] != None) :
# When list i are not null
position = i

i += 1

if (position != -1) :
# When need to sort list elements
source = -1
temp = position
# Find smallest node location of lists
i = position + 1
while (i < size) :
if (auxiliary[i] != None and auxiliary[i].data < auxiliary[temp].data) :
source = i
temp = i

i += 1

if (source != -1) :
temp = auxiliary[position].data
# Swap node value
auxiliary[position].data = auxiliary[source].data
auxiliary[source].data = temp
# after swap arrange second list elements in sorted order.
self.update_record(auxiliary[source])

# visit next node
auxiliary[position] = auxiliary[position].next
# Recursive executed, until when given list need sorting operation
self.sort(auxiliary, size)

# This function are handle the request to sort elements in given linked lists
# Assuming that given linked list contains sorted elements
def sort_list(self, lists, size) :
# This is used to store first node of each linked list
auxiliary = [None]*size
i = 0
# This loop are obtain the first node of each linked list
i = 0
while (i < size) :
# Get first node of lists
auxiliary[i] = lists[i]
i += 1

self.sort(auxiliary, size)
i = 0
# This loop are combining linked lists nodes
while (i < size - 1) :
i += 1
# This is not important but given multiple lists and each list are share their nudes to other
lists[i] = lists[0]

# This function are display given linked list elements
print(" ", head.data ," ", end = "")

def main() :
obj = DoublyList()
k = 4
lists = [None]*k

lists[0] = obj.insert(lists[0], 1)
# similar way add other elements
obj.insert(lists[0], 3)
obj.insert(lists[0], 14)
obj.insert(lists[0], 19)
lists[1] = obj.insert(lists[1], 0)
obj.insert(lists[1], 0)
obj.insert(lists[1], 2)
obj.insert(lists[1], 4)
lists[2] = obj.insert(lists[2], -3)
obj.insert(lists[2], 5)
obj.insert(lists[2], 8)
obj.insert(lists[2], 12)
obj.insert(lists[2], 12)
obj.insert(lists[2], 15)
obj.insert(lists[2], 17)
lists[3] = obj.insert(lists[3], 8)
obj.insert(lists[3], 15)
obj.insert(lists[3], 44)
obj.print_list(lists, k)
obj.sort_list(lists, k)
print(" After Sort \n ", end = "")
# After sort display the linked list elements
obj.display(lists[0])

if __name__ == "__main__": main()

Output

1   3   14   19
0   0   2   4
-3   5   8   12   12   15   17
8   15   44

After Sort
-3    0    0    1    2    3    4    5    8    8    12    12    14    15    15    17    19    44
# Ruby Program
# Merge K sorted linked lists
class Node

# Define the accessor and reader of class Node
attr_accessor :data, :next, :prev
def initialize(data)

self.data = data
self.next = nil
self.prev = nil
end
end
class DoublyList

# insert Node element of end of linked list

# Create a dynamic node
node = Node.new(value)
if (node == nil)

print("Memory overflow\n")
else

return node
else

# Find last node
while (temp != nil && temp.next != nil)

temp = temp.next
end
# Add new node to last position
temp.next = node
node.prev = temp
end
end
end
# This function are displayed group of given linked lists
def print_list(lists, size)

if (size <= 0)

else

temp = nil
i = 0
while (i < size)

temp = lists[i]
while (temp != nil)

print(" ", temp.data ,"")
temp = temp.next
end
print("\n")
i += 1
end
print("\n")
end
end
#  This function arrange the linked list node in sorted order
#  by using swapping node operation

temp = 0

end
end
# This function is sorted given linked list elements
def sort(auxiliary, size)

position = -1
source = -1
temp = 0
# Get first node position of given linked lists
i = 0
while (i < size && position == -1)

if (auxiliary[i] != nil)

# When list i are not null
position = i
end
i += 1
end
if (position != -1)

# When need to sort list elements
source = -1
temp = position
# Find smallest node location of lists
i = position + 1
while (i < size)

if (auxiliary[i] != nil && auxiliary[i].data < auxiliary[temp].data)

source = i
temp = i
end
i += 1
end
if (source != -1)

temp = auxiliary[position].data
# Swap node value
auxiliary[position].data = auxiliary[source].data
auxiliary[source].data = temp
# after swap arrange second list elements in sorted order.
self.update_record(auxiliary[source])
end
# visit next node
auxiliary[position] = auxiliary[position].next
# Recursive executed, until when given list need sorting operation
self.sort(auxiliary, size)
end
end
# This function are handle the request to sort elements in given linked lists
# Assuming that given linked list contains sorted elements
def sort_list(lists, size)

# This is used to store first node of each linked list
auxiliary = Array.new(size);
i = 0
# This loop are obtain the first node of each linked list
i = 0
while (i < size)

# Get first node of lists
auxiliary[i] = lists[i]
i += 1
end
self.sort(auxiliary, size)
i = 0
# This loop are combining linked lists nodes
while (i < size - 1)

i += 1
# This is not important but given multiple lists and each list are share their nudes to other
lists[i] = lists[0]
end
end
end
# This function are display given linked list elements

end
end
end
def main()

obj = DoublyList.new()
k = 4
lists = Array.new(k);
i = 0
while (i < k)

lists[i] = nil
i += 1
end
lists[0] = obj.insert(lists[0], 1)
# similar way add other elements
obj.insert(lists[0], 3)
obj.insert(lists[0], 14)
obj.insert(lists[0], 19)
lists[1] = obj.insert(lists[1], 0)
obj.insert(lists[1], 0)
obj.insert(lists[1], 2)
obj.insert(lists[1], 4)
lists[2] = obj.insert(lists[2], -3)
obj.insert(lists[2], 5)
obj.insert(lists[2], 8)
obj.insert(lists[2], 12)
obj.insert(lists[2], 12)
obj.insert(lists[2], 15)
obj.insert(lists[2], 17)
lists[3] = obj.insert(lists[3], 8)
obj.insert(lists[3], 15)
obj.insert(lists[3], 44)
obj.print_list(lists, k)
obj.sort_list(lists, k)
print(" After Sort \n ")
# After sort display the linked list elements
obj.display(lists[0])
end
main()

Output

1 3 14 19
0 0 2 4
-3 5 8 12 12 15 17
8 15 44

After Sort
-3  0  0  1  2  3  4  5  8  8  12  12  14  15  15  17  19  44
//Scala Program
class Node(var data: Int,
var next: Node,
var prev: Node)
{
def this(data: Int)
{
this(data, null, null);
}
}
class DoublyList
{
//insert Node element of end of linked list
def insert(head: Node, value: Int): Node = {
//Create a dynamic node
var node: Node = new Node(value);
if (node == null)
{
print("Memory overflow\n");
}
else
{
{
return node;
}
else
{
//Find last node
while (temp != null && temp.next != null)
{
temp = temp.next;
}
//Add new node to last position
temp.next = node;
node.prev = temp;
}
}
}
//This function are displayed group of given linked lists
def print_list(lists: Array[Node], size: Int): Unit = {
if (size <= 0)
{
}
else
{
var temp: Node = null;
var i: Int = 0;
while (i < size)
{
temp = lists(i);
while (temp != null)
{
print(" " + temp.data + "");
temp = temp.next;
}
print("\n");
i += 1;
}
print("\n");
}
}
// This function arrange the linked list node in sorted order
// by using swapping node operation
def update_record(head: Node): Unit = {
var temp: Int = 0;
while (auxiliary != null && auxiliary.next != null && auxiliary.next.data < head.data)
{
temp = auxiliary.data;
auxiliary.data = auxiliary.next.data;
auxiliary.next.data = temp;
auxiliary = auxiliary.next;
}
}
//This function is sorted given linked list elements
def sort(auxiliary: Array[Node], size: Int): Unit = {
var position: Int = -1;
var source: Int = -1;
var temp: Int = 0;
//Get first node position of given linked lists
var i: Int = 0;
while (i < size && position == -1)
{
if (auxiliary(i) != null)
{
//When list i are not null
position = i;
}
i += 1;
}
if (position != -1)
{
//When need to sort list elements
source = -1;
temp = position;
//Find smallest node location of lists
i = position + 1;
while (i < size)
{
if (auxiliary(i) != null && auxiliary(i).data < auxiliary(temp).data)
{
source = i;
temp = i;
}
i += 1;
}
if (source != -1)
{
temp = auxiliary(position).data;
//Swap node value
auxiliary(position).data = auxiliary(source).data;
auxiliary(source).data = temp;
//after swap arrange second list elements in sorted order.
update_record(auxiliary(source));
}
//visit next node
auxiliary(position) = auxiliary(position).next;
//Recursive executed, until when given list need sorting operation
sort(auxiliary, size);
}
}
//This function are handle the request to sort elements in given linked lists
//Assuming that given linked list contains sorted elements
def sort_list(lists: Array[Node], size: Int): Unit = {
//This is used to store first node of each linked list
var auxiliary: Array[Node] = new Array[Node](size);
var i: Int = 0;
//This loop are obtain the first node of each linked list
i = 0;
while (i < size)
{
//Get first node of lists
auxiliary(i) = lists(i);
i += 1;
}
sort(auxiliary, size);
i = 0;
//This loop are combining linked lists nodes
while (i < size - 1)
{
{
i += 1;
//This is not important but given multiple lists and each list are share their nudes to other
lists(i) = lists(0);
}
}
}
//This function are display given linked list elements
def display(head: Node): Unit = {
while (temp != null)
{
print(" " + temp.data + " ");
temp = temp.next;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: DoublyList = new DoublyList();
var k: Int = 4;
var lists: Array[Node] =  new Array[Node](k);
var i: Int = 0;
while (i < k)
{
lists(i) = null;
i += 1;
}
lists(0) = obj.insert(lists(0), 1);
obj.insert(lists(0), 3);
obj.insert(lists(0), 14);
obj.insert(lists(0), 19);
lists(1) = obj.insert(lists(1), 0);
obj.insert(lists(1), 0);
obj.insert(lists(1), 2);
obj.insert(lists(1), 4);
lists(2) = obj.insert(lists(2), -3);
obj.insert(lists(2), 5);
obj.insert(lists(2), 8);
obj.insert(lists(2), 12);
obj.insert(lists(2), 12);
obj.insert(lists(2), 15);
obj.insert(lists(2), 17);
lists(3) = obj.insert(lists(3), 8);
obj.insert(lists(3), 15);
obj.insert(lists(3), 44);
obj.print_list(lists, k);
obj.sort_list(lists, k);
print(" After Sort \n ");
//After sort display the linked list elements
obj.display(lists(0));
}
}

Output

1 3 14 19
0 0 2 4
-3 5 8 12 12 15 17
8 15 44

After Sort
-3  0  0  1  3  2  5  4  8  14  8  12  12  15  15  17  19  44
//Swift Program
class Node
{
var data: Int;
var next: Node? ;
var prev: Node? ;
init(_ data: Int)
{
self.data = data;
self.next = nil;
self.prev = nil;
}
}
class DoublyList
{
//insert Node element of end of linked list
func insert(_ head: inout Node? , _ value : Int)
{
//Create a dynamic node
let node: Node? = Node(value);
if (node == nil)
{
print("Memory overflow\n", terminator: "");
}
else
{
{
}
else
{
//Find last node
while (temp != nil && temp!.next != nil)
{
temp = temp!.next;
}
//Add new node to last position
temp!.next = node;
node!.prev = temp;
}
}

}
//This function are displayed group of given linked lists
func print_list(_ lists: [Node?], _ size: Int)
{
if (size <= 0)
{
}
else
{
var temp: Node? = nil;
var i: Int = 0;
while (i < size)
{

temp = lists[i];
while (temp != nil)
{
print(" ", temp!.data ,terminator: "");
temp = temp!.next;
}
print("\n", terminator: "");
i += 1;
}

}
}
// This function arrange the linked list node in sorted order
// by using swapping node operation
func update_record(_ front: Node? )
{
var temp: Int = 0;
var head : Node? = front;
{
}
}
//This function is sorted given linked list elements
func sort(_ auxiliary: inout[Node?], _ size: Int)
{
var position: Int = -1;
var source: Int = -1;
var temp: Int = 0;
//Get first node position of given linked lists
var i: Int = 0;
while (i < size && position == -1)
{
if (auxiliary[i] != nil)
{
//When list i are not null
position = i;
}
i += 1;
}
if (position != -1)
{
//When need to sort list elements
source = -1;
temp = position;
//Find smallest node location of lists
i = position + 1;
while (i < size)
{
if (auxiliary[i] != nil && auxiliary[i]!.data < auxiliary[temp]!.data)
{
source = i;
temp = i;
}
i += 1;
}
if (source != -1)
{
temp = auxiliary[position]!.data;
//Swap node value
auxiliary[position]!.data = auxiliary[source]!.data;
auxiliary[source]!.data = temp;
//after swap arrange second list elements in sorted order.
self.update_record(auxiliary[source]);
}
//visit next node
auxiliary[position] = auxiliary[position]!.next;
//Recursive executed, until when given list need sorting operation
self.sort(&auxiliary, size);
}
}
//This function are handle the request to sort elements in given linked lists
//Assuming that given linked list contains sorted elements
func sort_list(_ lists: inout[Node? ], _ size: Int)
{
//This is used to store first node of each linked list
var auxiliary: [Node?] = [Node]() ;
var i: Int = 0;
//This loop are obtain the first node of each linked list
i = 0;
while (i < size)
{
//Get first node of lists
auxiliary.append(lists[i]);
i += 1;
}
self.sort(&auxiliary, size);
i = 0;
//This loop are combining linked lists nodes
while (i < size - 1)
{
{
i += 1;
//This is not important but given multiple lists and each list are share their nudes to other
lists[i] = lists[0];
}
}
}
//This function are display given linked list elements
{
var temp : Node? = head;
while (temp != nil)
{
print(" ", temp!.data ," ", terminator: "");
temp = temp!.next;
}
}
}
func main()
{
let obj: DoublyList = DoublyList();
let k: Int = 4;
var lists: [Node?] =  [Node]() ;
var i: Int = 0;
while (i < k)
{
lists.append(nil);
i += 1;
}

obj.insert(&lists[0], 1);
obj.insert(&lists[0], 3);
obj.insert(&lists[0], 14);
obj.insert(&lists[0], 19);
obj.insert(&lists[1], 0);
obj.insert(&lists[1], 0);
obj.insert(&lists[1], 2);
obj.insert(&lists[1], 4);
obj.insert(&lists[2], -3);
obj.insert(&lists[2], 5);
obj.insert(&lists[2], 8);
obj.insert(&lists[2], 12);
obj.insert(&lists[2], 12);
obj.insert(&lists[2], 15);
obj.insert(&lists[2], 17);
obj.insert(&lists[3], 8);
obj.insert(&lists[3], 15);
obj.insert(&lists[3], 44);

obj.print_list(lists, k);
obj.sort_list(&lists, k);
print(" After Sort  ");
//After sort display the linked list elements
obj.display(lists[0]);

}
main();

Output

1  3  14  19
0  0  2  4
-3  5  8  12  12  15  17
8  15  44
After Sort
-3    0    0    1    2    3    4    5    8    8    12    12    14    15    15    17    19    44

Time Complexity

• The algorithm iterates through all elements of the K lists exactly once.
• For each element, inserting into the min-heap takes O(log K) time.
• Therefore, the overall time complexity of the algorithm is O(N * log K), where N is the total number of elements across all K linked lists.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post