Posted on by Kalkicode
Code Doubly linked list

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.

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.

New Comment