Merge K sorted linked lists
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
Return the merged linked list
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
//Merge K sorted linked lists
#include <stdio.h>
#include <stdlib.h> //for malloc function
//Structure of doubly linked list
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;
if ( *head == NULL)
{
*head = node;
}
else
{
struct Node *temp = *head;
//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)
{
printf("Empty linked list");
}
else
{
struct Node *temp = NULL;
for (int i = 0; i < size; i++)
{
temp = list[i];
//Traverse doubly linked list
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
void update_record(struct Node *head)
{
int temp = 0;
//Sort given linked list
while (head != NULL && head->next != NULL && head->next->data < head->data)
{
temp = head->data;
head->data = head->next->data;
head->next->data = temp;
head = head->next;
}
}
//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);
struct Node *head = list[0];
i = 0;
//This loop are combining linked lists nodes
while (i < size - 1)
{
if (head->next == NULL)
{
i++;
head->next = list[i];
//This is not important but given multiple lists and each list are share their nudes to other
list[i] = list[0];
}
head = head->next;
}
}
//This function are display given linked list elements
void display(struct Node *head)
{
while (head != NULL)
{
//print node value
printf("%3d", head->data);
head = head->next;
}
}
int main()
{
struct Node *list[4] = {
NULL
};
//Add Linked list elements
//Add first list element
insert( & list[0], 1);
//similar way add other elements
insert( & list[0], 3);
insert( & list[0], 14);
insert( & list[0], 19);
//Add second list element
insert( & list[1], 0);
insert( & list[1], 0);
insert( & list[1], 2);
insert( & list[1], 4);
//Add third list element
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);
//Add fourth list element
insert( & list[3], 8);
insert( & list[3], 15);
insert( & list[3], 44);
//Get size of linked list
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
//Merge K sorted linked lists
//Doubly linked list node
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
{
if (head == null)
{
return node;
}
else
{
Node temp = head;
//Find last node
while (temp != null && temp.next != null)
{
temp = temp.next;
}
//Add new node to last position
temp.next = node;
node.prev = temp;
}
}
return head;
}
//This function are displayed group of given linked lists
public void print_list(Node[] lists, int size)
{
if (size <= 0)
{
System.out.print("Empty linked list");
}
else
{
Node temp = null;
for (int i = 0; i < size; i++)
{
temp = lists[i];
//Traverse doubly linked list
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
public void update_record(Node head)
{
int temp = 0;
//Sort given linked list
while (head != null && head.next != null && head.next.data < head.data)
{
temp = head.data;
head.data = head.next.data;
head.next.data = temp;
head = head.next;
}
}
//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);
Node head = lists[0];
i = 0;
//This loop are combining linked lists nodes
while (i < size - 1)
{
if (head.next == null)
{
i++;
head.next = lists[i];
//This is not important but given multiple lists and each list are share their nudes to other
lists[i] = lists[0];
}
head = head.next;
}
}
//This function are display given linked list elements
public void display(Node head)
{
while (head != null)
{
System.out.print(" " + head.data + " ");
head = head.next;
}
}
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;
}
//Add Linked list elements
//Add first list element
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);
//Add second list element
lists[1]=obj.insert(lists[1], 0);
obj.insert(lists[1], 0);
obj.insert(lists[1], 2);
obj.insert(lists[1], 4);
//Add third list element
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);
//Add fourth list element
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 header file
#include <iostream>
using namespace std;
//C++ Program
//Merge K sorted linked lists
//Doubly linked list node
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
{
if (head == NULL)
{
return node;
}
else
{
Node * temp = head;
//Find last node
while (temp != NULL && temp->next != NULL)
{
temp = temp->next;
}
//Add new node to last position
temp->next = node;
node->prev = temp;
}
}
return head;
}
//This function are displayed group of given linked lists
void print_list(Node* lists[], int size)
{
if (size <= 0)
{
cout << "Empty linked list";
}
else
{
Node * temp = NULL;
for (int i = 0; i < size; i++)
{
temp = lists[i];
//Traverse doubly linked list
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
void update_record(Node * head)
{
int temp = 0;
//Sort given linked list
while (head != NULL && head->next != NULL && head->next->data < head->data)
{
temp = head->data;
head->data = head->next->data;
head->next->data = temp;
head = head->next;
}
}
//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);
Node * head = lists[0];
i = 0;
//This loop are combining linked lists nodes
while (i < size - 1)
{
if (head->next == NULL)
{
i++;
head->next = lists[i];
//This is not important but given multiple lists and each list are share their nudes to other
lists[i] = lists[0];
}
head = head->next;
}
}
//This function are display given linked list elements
void display(Node * head)
{
while (head != NULL)
{
cout << " " << head->data << " ";
head = head->next;
}
}
};
int main()
{
DoublyList obj = DoublyList();
int k = 4;
Node * lists[4];
for (int i = 0; i < k; i++)
{
lists[i] = NULL;
}
//Add Linked list elements
//Add first list element
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);
//Add second list element
lists[1] = obj.insert(lists[1], 0);
obj.insert(lists[1], 0);
obj.insert(lists[1], 2);
obj.insert(lists[1], 4);
//Add third list element
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);
//Add fourth list element
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
//Merge K sorted linked lists
//Doubly linked list node
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
{
if (head == null)
{
return node;
}
else
{
Node temp = head;
//Find last node
while (temp != null && temp.next != null)
{
temp = temp.next;
}
//Add new node to last position
temp.next = node;
node.prev = temp;
}
}
return head;
}
//This function are displayed group of given linked lists
public void print_list(Node[] lists, int size)
{
if (size <= 0)
{
Console.Write("Empty linked list");
}
else
{
Node temp = null;
for (int i = 0; i < size; i++)
{
temp = lists[i];
//Traverse doubly linked list
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
public void update_record(Node head)
{
int temp = 0;
//Sort given linked list
while (head != null && head.next != null && head.next.data < head.data)
{
temp = head.data;
head.data = head.next.data;
head.next.data = temp;
head = head.next;
}
}
//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);
Node head = lists[0];
i = 0;
//This loop are combining linked lists nodes
while (i < size - 1)
{
if (head.next == null)
{
i++;
head.next = lists[i];
//This is not important but given multiple lists and each list are share their nudes to other
lists[i] = lists[0];
}
head = head.next;
}
}
//This function are display given linked list elements
public void display(Node head)
{
while (head != null)
{
Console.Write(" " + head.data + " ");
head = head.next;
}
}
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;
}
//Add Linked list elements
//Add first list element
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);
//Add second list element
lists[1] = obj.insert(lists[1], 0);
obj.insert(lists[1], 0);
obj.insert(lists[1], 2);
obj.insert(lists[1], 4);
//Add third list element
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);
//Add fourth list element
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
//Merge K sorted linked lists
//Doubly linked list node
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
public function insert($head, $value)
{
//Create a dynamic node
$node = new Node($value);
if ($node == null)
{
echo "Memory overflow\n";
}
else
{
if ($head == null)
{
return $node;
}
else
{
$temp = $head;
//Find last node
while ($temp != null && $temp->next != null)
{
$temp = $temp->next;
}
//Add new node to last position
$temp->next = $node;
$node->prev = $temp;
}
}
return $head;
}
//This function are displayed group of given linked lists
public function print_list( & $lists, $size)
{
if ($size <= 0)
{
echo "Empty linked list";
}
else
{
$temp = null;
for ($i = 0; $i < $size; $i++)
{
$temp = $lists[$i];
//Traverse doubly linked list
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
public function update_record($head)
{
$temp = 0;
//Sort given linked list
while ($head != null && $head->next != null && $head->next->data < $head->data)
{
$temp = $head->data;
$head->data = $head->next->data;
$head->next->data = $temp;
$head = $head->next;
}
}
//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);
$head = $lists[0];
$i = 0;
//This loop are combining linked lists nodes
while ($i < $size - 1)
{
if ($head->next == null)
{
$i++;
$head->next = $lists[$i];
//This is not important but given multiple lists and each list are share their nudes to other
$lists[$i] = $lists[0];
}
$head = $head->next;
}
}
//This function are display given linked list elements
public function display($head)
{
while ($head != null)
{
echo " ". $head->data ." ";
$head = $head->next;
}
}
}
function main()
{
$obj = new DoublyList();
$k = 4;
$lists = array_fill(0, 4, null);
for ($i = 0; $i < $k; $i++)
{
$lists[$i] = null;
}
//Add Linked list elements
//Add first list element
$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);
//Add second list element
$lists[1] = $obj->insert($lists[1], 0);
$obj->insert($lists[1], 0);
$obj->insert($lists[1], 2);
$obj->insert($lists[1], 4);
//Add third list element
$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);
//Add fourth list element
$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
//Merge K sorted linked lists
//Doubly linked list node
class Node
{
constructor(data)
{
this.data = data;
this.next = null;
this.prev = null;
}
}
class DoublyList
{
//insert Node element of end of linked list
insert(head, value)
{
//Create a dynamic node
var node = new Node(value);
if (node == null)
{
process.stdout.write("Memory overflow\n");
}
else
{
if (head == null)
{
return node;
}
else
{
var temp = head;
//Find last node
while (temp != null && temp.next != null)
{
temp = temp.next;
}
//Add new node to last position
temp.next = node;
node.prev = temp;
}
}
return head;
}
//This function are displayed group of given linked lists
print_list(lists, size)
{
if (size <= 0)
{
process.stdout.write("Empty linked list");
}
else
{
var temp = null;
for (var i = 0; i < size; i++)
{
temp = lists[i];
//Traverse doubly linked list
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
update_record(head)
{
var temp = 0;
//Sort given linked list
while (head != null && head.next != null && head.next.data < head.data)
{
temp = head.data;
head.data = head.next.data;
head.next.data = temp;
head = head.next;
}
}
//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);
var head = lists[0];
i = 0;
//This loop are combining linked lists nodes
while (i < size - 1)
{
if (head.next == null)
{
i++;
head.next = lists[i];
//This is not important but given multiple lists and each list are share their nudes to other
lists[i] = lists[0];
}
head = head.next;
}
}
//This function are display given linked list elements
display(head)
{
while (head != null)
{
process.stdout.write(" " + head.data + " ");
head = head.next;
}
}
}
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;
}
//Add Linked list elements
//Add first list element
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);
//Add second list element
lists[1] = obj.insert(lists[1], 0);
obj.insert(lists[1], 0);
obj.insert(lists[1], 2);
obj.insert(lists[1], 4);
//Add third list element
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);
//Add fourth list element
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
# Doubly linked list node
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
def insert(self, head, value) :
# Create a dynamic node
node = Node(value)
if (node == None) :
print("Memory overflow\n", end = "")
else :
if (head == None) :
return node
else :
temp = head
# 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
return head
# 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]
# Traverse doubly linked list
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
def update_record(self, head) :
temp = 0
# Sort given linked list
while (head != None and head.next != None and head.next.data < head.data) :
temp = head.data
head.data = head.next.data
head.next.data = temp
head = head.next
# 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)
head = lists[0]
i = 0
# This loop are combining linked lists nodes
while (i < size - 1) :
if (head.next == None) :
i += 1
head.next = lists[i]
# This is not important but given multiple lists and each list are share their nudes to other
lists[i] = lists[0]
head = head.next
# This function are display given linked list elements
def display(self, head) :
while (head != None) :
print(" ", head.data ," ", end = "")
head = head.next
def main() :
obj = DoublyList()
k = 4
lists = [None]*k
# Add Linked list elements
# Add first list element
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)
# Add second list element
lists[1] = obj.insert(lists[1], 0)
obj.insert(lists[1], 0)
obj.insert(lists[1], 2)
obj.insert(lists[1], 4)
# Add third list element
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)
# Add fourth list element
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
# Doubly linked list node
class Node
# Define the accessor and reader of class Node
attr_reader :data, :next, :prev
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
def insert(head, value)
# Create a dynamic node
node = Node.new(value)
if (node == nil)
print("Memory overflow\n")
else
if (head == nil)
return node
else
temp = head
# 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
return head
end
# This function are displayed group of given linked lists
def print_list(lists, size)
if (size <= 0)
print("Empty linked list")
else
temp = nil
i = 0
while (i < size)
temp = lists[i]
# Traverse doubly linked list
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
def update_record(head)
temp = 0
# Sort given linked list
while (head != nil && head.next != nil && head.next.data < head.data)
temp = head.data
head.data = head.next.data
head.next.data = temp
head = head.next
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)
head = lists[0]
i = 0
# This loop are combining linked lists nodes
while (i < size - 1)
if (head.next == nil)
i += 1
head.next = lists[i]
# This is not important but given multiple lists and each list are share their nudes to other
lists[i] = lists[0]
end
head = head.next
end
end
# This function are display given linked list elements
def display(head)
while (head != nil)
print(" ", head.data ," ")
head = head.next
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
# Add Linked list elements
# Add first list element
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)
# Add second list element
lists[1] = obj.insert(lists[1], 0)
obj.insert(lists[1], 0)
obj.insert(lists[1], 2)
obj.insert(lists[1], 4)
# Add third list element
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)
# Add fourth list element
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
//Merge K sorted linked lists
//Doubly linked list node
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
{
if (head == null)
{
return node;
}
else
{
var temp: Node = head;
//Find last node
while (temp != null && temp.next != null)
{
temp = temp.next;
}
//Add new node to last position
temp.next = node;
node.prev = temp;
}
}
return head;
}
//This function are displayed group of given linked lists
def print_list(lists: Array[Node], size: Int): Unit = {
if (size <= 0)
{
print("Empty linked list");
}
else
{
var temp: Node = null;
var i: Int = 0;
while (i < size)
{
temp = lists(i);
//Traverse doubly linked list
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;
var auxiliary = head;
//Sort given linked list
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);
var head: Node = lists(0);
i = 0;
//This loop are combining linked lists nodes
while (i < size - 1)
{
if (head.next == null)
{
i += 1;
head.next = lists(i);
//This is not important but given multiple lists and each list are share their nudes to other
lists(i) = lists(0);
}
head = head.next;
}
}
//This function are display given linked list elements
def display(head: Node): Unit = {
var temp = head;
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;
}
//Add Linked list elements
//Add first list element
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);
//Add second list element
lists(1) = obj.insert(lists(1), 0);
obj.insert(lists(1), 0);
obj.insert(lists(1), 2);
obj.insert(lists(1), 4);
//Add third list element
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);
//Add fourth list element
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
//Merge K sorted linked lists
//Doubly linked list node
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
{
if (head == nil)
{
head = node;
}
else
{
var temp: Node? = head;
//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)
{
print("Empty linked list");
}
else
{
var temp: Node? = nil;
var i: Int = 0;
while (i < size)
{
temp = lists[i];
//Traverse doubly linked list
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;
//Sort given linked list
while (head != nil && head!.next != nil && head!.next!.data < head!.data)
{
temp = head!.data;
head!.data = head!.next!.data;
head!.next!.data = temp;
head = head!.next;
}
}
//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);
var head: Node? = lists[0];
i = 0;
//This loop are combining linked lists nodes
while (i < size - 1)
{
if (head!.next == nil)
{
i += 1;
head!.next = lists[i];
//This is not important but given multiple lists and each list are share their nudes to other
lists[i] = lists[0];
}
head = head!.next;
}
}
//This function are display given linked list elements
func display(_ head: Node? )
{
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;
}
//Add Linked list elements
//Add first list element
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);
//Add second list element
obj.insert(&lists[1], 0);
obj.insert(&lists[1], 0);
obj.insert(&lists[1], 2);
obj.insert(&lists[1], 4);
//Add third list element
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);
//Add fourth list element
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.
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.
New Comment