Sort linked list using recursion

Here given code implementation process.

// C Program
// Sort linked list using recursion
#include <stdio.h>

#include <stdlib.h>

//Define structure of custom linked list
struct Node
{
	int data;
	struct Node *next;
};
//Insert a node in given linked list
void insert(struct Node **head, int value)
{
	//Create a node
	struct Node *node = (struct Node *) malloc(sizeof(struct Node));
	if (node == NULL)
	{
		printf("Memory overflow\n");
	}
	else
	{
		node->data = value;
		node->next = *head;*head = node;
	}
}
//This function are add new linked list element in sorted position
void sorted_merge(struct Node *current, struct Node *element)
{
	if (current->next == NULL)
	{ //Add element at the end
		current->next = element;
	}
	else if (current->next->data >= element->data)
	{
		element->next = current->next;
		current->next = element;
	}
	else
	{
		sorted_merge(current->next, element);
	}
}
//Sorting the linked list elements using recursion
void sort(struct Node **head)
{
	//Base case   
	if ( *head == NULL || ( *head)->next == NULL)
	{
		//When linked list is empty or only one element
		return;
	}
	//Get head element of linked list
	struct Node *element = ( *head);
	//Modify the head element of linked list
	( *head) = element->next;
	//Separate previous head element
	element->next = NULL;
	//Recursively executing sort process
	sort(head);
	if (element->data <= ( *head)->data)
	{
		//Get a smallest Element
		element->next = ( *head);*head = element;
	}
	else
	{
		//Add element in sorted position
		sorted_merge( *head, element);
	}
}
//Display element of Node
void display(struct Node *head)
{
	while (head != NULL)
	{
		printf("%d  ", head->data);
		head = head->next;
	}
}
int main()
{
	struct Node *head = NULL;
	//Add element
	insert( & head, 16);
	insert( & head, 42);
	insert( & head, 3);
	insert( & head, 22);
	insert( & head, -5);
	insert( & head, 8);
	insert( & head, 5);
	insert( & head, 15);
	printf("\n Before Sort : ");
	display(head);
	sort( & head);
	printf("\n After Sort : ");
	display(head);
}

Output

 Before Sort : 15  5  8  -5  22  3  42  16
 After Sort : -5  3  5  8  15  16  22  42
// Java Program 
// Sort linked list using recursion
// Linked List node
class Node
{
	//Define linked list node elements
	public int data;
	public Node next;
	public Node(int data, Node next_node)
	{
		//set values of linked list
		this.data = data;
		this.next = next_node;
	}
}
class MyLinkedList
{
	public Node head;
	//Class constructors LinkedList
	MyLinkedList()
	{
		this.head = null;
	}
	//insert newly element
	public void insert(int data)
	{
		//Make a new node of linked list
		Node node = new Node(data, this.head);
		if (node != null)
		{
			//Make a new head
			this.head = node;
		}
	}
	//display all Linked List elements
	public void display()
	{
		if (head != null)
		{
			Node temp = head;
			//iterating Linked List node elements, from the first node to last node
			while (temp != null)
			{
				// Display node values
				System.out.print("  " + temp.data);
				// Visit to next node
				temp = temp.next;
			}
			System.out.print("\n");
		}
		else
		{
			System.out.println("Empty Linked list");
		}
	}
	//This function are add new linked list element in sorted position
	public void sorted_merge(Node current, Node element)
	{
		if (current.next == null)
		{
			//Add element at the end
			current.next = element;
		}
		else if (current.next.data >= element.data)
		{
			element.next = current.next;
			current.next = element;
		}
		else
		{
			sorted_merge(current.next, element);
		}
	}
	//Sorting the linked list elements using recursion
	public void sort()
	{
		//Base case   
		if (this.head == null || this.head.next == null)
		{
			//When linked list is empty or only one element
			return;
		}
		//Get head element of linked list
		Node element = this.head;
		//Modify the head element of linked list
		this.head = element.next;
		//Separate previous head element
		element.next = null;
		//Recursively executing sort process
		this.sort();
		if (element.data <= this.head.data)
		{
			//Get a smallest Element
			element.next = this.head;
			this.head = element;
		}
		else
		{
			//Add element in sorted position
			sorted_merge(this.head, element);
		}
	}
	public static void main(String[] args)
	{
		MyLinkedList obj = new MyLinkedList();
		//Add element
		obj.insert(16);
		obj.insert(42);
		obj.insert(3);
		obj.insert(22);
		obj.insert(-5);
		obj.insert(8);
		obj.insert(5);
		obj.insert(15);
		System.out.print("\n Before Sort : ");
		obj.display();
		obj.sort();
		System.out.print("\n After Sort : ");
		obj.display();
	}
}

Output

 Before Sort :   15  5  8  -5  22  3  42  16

 After Sort :   -5  3  5  8  15  16  22  42
//Include header file
#include <iostream>

using namespace std;
// C++ Program 
// Sort linked list using recursion
// Linked List node
class Node
{
	public:
	//Define linked list node elements
	int data;
	Node * next;
	Node(int data, Node * next_node)
	{
		//set values of linked list
		this->data = data;
		this->next = next_node;
	}
};
class MyLinkedList
{
	public: Node * head;
	//Class constructors LinkedList
	MyLinkedList()
	{
		this->head = NULL;
	}
	//insert newly element
	void insert(int data)
	{
		//Make a new node of linked list
		Node * node = new Node(data, this->head);
		if (node != NULL)
		{
			//Make a new head
			this->head = node;
		}
	}
	//display all Linked List elements
	void display()
	{
		if (this->head != NULL)
		{
			Node * temp = this->head;
			//iterating Linked List node elements, from the first node to last node
			while (temp != NULL)
			{
				// Display node values
				cout << "  " << temp->data;
				// Visit to next node
				temp = temp->next;
			}
			cout << "\n";
		}
		else
		{
			cout << "Empty Linked list";
		}
	}
	//This function are add new linked list element in sorted position
	void sorted_merge(Node * current, Node * element)
	{
		if (current->next == NULL)
		{
			//Add element at the end
			current->next = element;
		}
		else if (current->next->data >= element->data)
		{
			element->next = current->next;
			current->next = element;
		}
		else
		{
			this->sorted_merge(current->next, element);
		}
	}
	//Sorting the linked list elements using recursion
	void sort()
	{
		//Base case   
		if (this->head == NULL || this->head->next == NULL)
		{
			//When linked list is empty or only one element
			return;
		}
		//Get head element of linked list
		Node * element = this->head;
		//Modify the head element of linked list
		this->head = element->next;
		//Separate previous head element
		element->next = NULL;
		//Recursively executing sort process
		this->sort();
		if (element->data <= this->head->data)
		{
			//Get a smallest Element
			element->next = this->head;
			this->head = element;
		}
		else
		{
			//Add element in sorted position
			this->sorted_merge(this->head, element);
		}
	}
};
int main()
{
	MyLinkedList obj = MyLinkedList();
	//Add element
	obj.insert(16);
	obj.insert(42);
	obj.insert(3);
	obj.insert(22);
	obj.insert(-5);
	obj.insert(8);
	obj.insert(5);
	obj.insert(15);
	cout << "\n Before Sort : ";
	obj.display();
	obj.sort();
	cout << "\n After Sort : ";
	obj.display();
	return 0;
}

Output

 Before Sort :   15  5  8  -5  22  3  42  16

 After Sort :   -5  3  5  8  15  16  22  42
//Include namespace system
using System;
// C# Program 
// Sort linked list using recursion
// Linked List node
class Node
{
	//Define linked list node elements
	public int data;
	public Node next;
	public Node(int data, Node next_node)
	{
		//set values of linked list
		this.data = data;
		this.next = next_node;
	}
}
class MyLinkedList
{
	public Node head;
	//Class constructors LinkedList
	MyLinkedList()
	{
		this.head = null;
	}
	//insert newly element
	public void insert(int data)
	{
		//Make a new node of linked list
		Node node = new Node(data, this.head);
		if (node != null)
		{
			//Make a new head
			this.head = node;
		}
	}
	//display all Linked List elements
	public void display()
	{
		if (head != null)
		{
			Node temp = head;
			//iterating Linked List node elements, from the first node to last node
			while (temp != null)
			{
				// Display node values
				Console.Write("  " + temp.data);
				// Visit to next node
				temp = temp.next;
			}
			Console.Write("\n");
		}
		else
		{
			Console.WriteLine("Empty Linked list");
		}
	}
	//This function are add new linked list element in sorted position
	public void sorted_merge(Node current, Node element)
	{
		if (current.next == null)
		{
			//Add element at the end
			current.next = element;
		}
		else if (current.next.data >= element.data)
		{
			element.next = current.next;
			current.next = element;
		}
		else
		{
			sorted_merge(current.next, element);
		}
	}
	//Sorting the linked list elements using recursion
	public void sort()
	{
		//Base case   
		if (this.head == null || this.head.next == null)
		{
			//When linked list is empty or only one element
			return;
		}
		//Get head element of linked list
		Node element = this.head;
		//Modify the head element of linked list
		this.head = element.next;
		//Separate previous head element
		element.next = null;
		//Recursively executing sort process
		this.sort();
		if (element.data <= this.head.data)
		{
			//Get a smallest Element
			element.next = this.head;
			this.head = element;
		}
		else
		{
			//Add element in sorted position
			sorted_merge(this.head, element);
		}
	}
	public static void Main(String[] args)
	{
		MyLinkedList obj = new MyLinkedList();
		//Add element
		obj.insert(16);
		obj.insert(42);
		obj.insert(3);
		obj.insert(22);
		obj.insert(-5);
		obj.insert(8);
		obj.insert(5);
		obj.insert(15);
		Console.Write("\n Before Sort : ");
		obj.display();
		obj.sort();
		Console.Write("\n After Sort : ");
		obj.display();
	}
}

Output

 Before Sort :   15  5  8  -5  22  3  42  16

 After Sort :   -5  3  5  8  15  16  22  42
<?php
// Php Program 
// Sort linked list using recursion
// Linked List node
class Node
{
	//Define linked list node elements
	public $data;
	public $next;

	function __construct($data, $next_node)
	{
		//set values of linked list
		$this->data = $data;
		$this->next = $next_node;
	}
}
class MyLinkedList
{
	public $head;
	//Class constructors LinkedList
	function __construct()
	{
		$this->head = null;
	}
	//insert newly element
	public	function insert($data)
	{
		//Make a new node of linked list
		$node = new Node($data, $this->head);
		if ($node != null)
		{
			//Make a new head
			$this->head = $node;
		}
	}
	//display all Linked List elements
	public	function display()
	{
		if ($this->head != null)
		{
			$temp = $this->head;
			//iterating Linked List node elements, from the first node to last node
			while ($temp != null)
			{
				echo "  ". $temp->data;
				// Visit to next node
				$temp = $temp->next;
			}
			echo "\n";
		}
		else
		{
			echo "Empty Linked list";
		}
	}
	//This function are add new linked list element in sorted position
	public	function sorted_merge($current, $element)
	{
		if ($current->next == null)
		{
			//Add element at the end
			$current->next = $element;
		}
		else if ($current->next->data >= $element->data)
		{
			$element->next = $current->next;
			$current->next = $element;
		}
		else
		{
			$this->sorted_merge($current->next, $element);
		}
	}
	//Sorting the linked list elements using recursion
	public	function sort()
	{
		//Base case   
		if ($this->head == null || $this->head->next == null)
		{
			//When linked list is empty or only one element
			return;
		}
		//Get head element of linked list
		$element = $this->head;
		//Modify the head element of linked list
		$this->head = $element->next;
		//Separate previous head element
		$element->next = null;
		//Recursively executing sort process
		$this->sort();
		if ($element->data <= $this->head->data)
		{
			//Get a smallest Element
			$element->next = $this->head;
			$this->head = $element;
		}
		else
		{
			//Add element in sorted position
			$this->sorted_merge($this->head, $element);
		}
	}
}

function main()
{
	$obj = new MyLinkedList();
	//Add element
	$obj->insert(16);
	$obj->insert(42);
	$obj->insert(3);
	$obj->insert(22);
	$obj->insert(-5);
	$obj->insert(8);
	$obj->insert(5);
	$obj->insert(15);
	echo "\n Before Sort : ";
	$obj->display();
	$obj->sort();
	echo "\n After Sort : ";
	$obj->display();
}
main();

Output

 Before Sort :   15  5  8  -5  22  3  42  16

 After Sort :   -5  3  5  8  15  16  22  42
// Node Js Program 
// Sort linked list using recursion
// Linked List node
class Node
{
	//Define linked list node elements
	constructor(data, next_node)
	{
		//set values of linked list
		this.data = data;
		this.next = next_node;
	}
}
class MyLinkedList
{
	//Class constructors LinkedList
	constructor()
	{
		this.head = null;
	}
	//insert newly element
	insert(data)
	{
		//Make a new node of linked list
		var node = new Node(data, this.head);
		if (node != null)
		{
			//Make a new head
			this.head = node;
		}
	}
	//display all Linked List elements
	display()
	{
		if (this.head != null)
		{
			var temp = this.head;
			//iterating Linked List node elements, from the first node to last node
			while (temp != null)
			{
				process.stdout.write("  " + temp.data);
				// Visit to next node
				temp = temp.next;
			}
			process.stdout.write("\n");
		}
		else
		{
			process.stdout.write("Empty Linked list");
		}
	}
	//This function are add new linked list element in sorted position
	sorted_merge(current, element)
	{
		if (current.next == null)
		{
			//Add element at the end
			current.next = element;
		}
		else if (current.next.data >= element.data)
		{
			element.next = current.next;
			current.next = element;
		}
		else
		{
			this.sorted_merge(current.next, element);
		}
	}
	//Sorting the linked list elements using recursion
	sort()
	{
		//Base case   
		if (this.head == null || this.head.next == null)
		{
			//When linked list is empty or only one element
			return;
		}
		//Get head element of linked list
		var element = this.head;
		//Modify the head element of linked list
		this.head = element.next;
		//Separate previous head element
		element.next = null;
		//Recursively executing sort process
		this.sort();
		if (element.data <= this.head.data)
		{
			//Get a smallest Element
			element.next = this.head;
			this.head = element;
		}
		else
		{
			//Add element in sorted position
			this.sorted_merge(this.head, element);
		}
	}
}

function main()
{
	var obj = new MyLinkedList();
	//Add element
	obj.insert(16);
	obj.insert(42);
	obj.insert(3);
	obj.insert(22);
	obj.insert(-5);
	obj.insert(8);
	obj.insert(5);
	obj.insert(15);
	process.stdout.write("\n Before Sort : ");
	obj.display();
	obj.sort();
	process.stdout.write("\n After Sort : ");
	obj.display();
}
main();

Output

 Before Sort :   15  5  8  -5  22  3  42  16

 After Sort :   -5  3  5  8  15  16  22  42
#  Python 3 Program 
#  Sort linked list using recursion

#  Linked List node
class Node :
	# Define linked list node elements
	
	def __init__(self, data, next_node) :
		# set values of linked list
		self.data = data
		self.next = next_node
	

class MyLinkedList :
	
	# Class constructors LinkedList
	def __init__(self) :
		self.head = None
	
	# insert newly element
	def insert(self, data) :
		# Make a new node of linked list
		node = Node(data, self.head)
		if (node != None) :
			# Make a new head
			self.head = node
		
	
	# display all Linked List elements
	def display(self) :
		if (self.head != None) :
			temp = self.head
			# iterating Linked List node elements, from the first node to last node
			while (temp != None) :
				print("  ", temp.data, end = "")
				#  Visit to next node
				temp = temp.next
			
			print("\n", end = "")
		else :
			print("Empty Linked list", end = "")
		
	
	# This function are add new linked list element in sorted position
	def sorted_merge(self, current, element) :
		if (current.next == None) :
			# Add element at the end
			current.next = element
		
		elif(current.next.data >= element.data) :
			element.next = current.next
			current.next = element
		else :
			self.sorted_merge(current.next, element)
		
	
	# Sorting the linked list elements using recursion
	def sort(self) :
		# Base case   
		if (self.head == None or self.head.next == None) :
			# When linked list is empty or only one element
			return
		
		# Get head element of linked list
		element = self.head
		# Modify the head element of linked list
		self.head = element.next
		# Separate previous head element
		element.next = None
		# Recursively executing sort process
		self.sort()
		if (element.data <= self.head.data) :
			# Get a smallest Element
			element.next = self.head
			self.head = element
		else :
			# Add element in sorted position
			self.sorted_merge(self.head, element)
		
	

def main() :
	obj = MyLinkedList()
	# Add element
	obj.insert(16)
	obj.insert(42)
	obj.insert(3)
	obj.insert(22)
	obj.insert(-5)
	obj.insert(8)
	obj.insert(5)
	obj.insert(15)
	print("\n Before Sort : ", end = "")
	obj.display()
	obj.sort()
	print("\n After Sort : ", end = "")
	obj.display()

if __name__ == "__main__": main()

Output

 Before Sort :    15   5   8   -5   22   3   42   16

 After Sort :    -5   3   5   8   15   16   22   42
#  Ruby Program 
#  Sort linked list using recursion

#  Linked List node
class Node 

	# Define the accessor and reader of class Node  
	attr_reader :data, :next
	attr_accessor :data, :next

	# Define linked list node elements
	def initialize(data, next_node)
	
		# set values of linked list
		self.data = data
		self.next = next_node
	end
end
class MyLinkedList 

	# Define the accessor and reader of class MyLinkedList  
	attr_reader :head
	attr_accessor :head

	# Class constructors LinkedList
	def initialize()
		self.head = nil
	end
	# insert newly element
	def insert(data)
	
		# Make a new node of linked list
		node = Node.new(data, self.head)
		if (node != nil)
		
			# Make a new head
			self.head = node
		end
	end
	# display all Linked List elements
	def display()
	
		if (@head != nil)
		
			temp = @head
			# iterating Linked List node elements, from the first node to last node
			while (temp != nil)
			
				#  Display node values
				print("  ", temp.data)
				#  Visit to next node
				temp = temp.next
			end
			print("\n")
		else
		
			print("Empty Linked list")
		end
	end
	# This function are add new linked list element in sorted position
	def sorted_merge(current, element)
	
		if (current.next == nil)
		
			# Add element at the end
			current.next = element
		elsif(current.next.data >= element.data)
		
			element.next = current.next
			current.next = element
		else
		
			self.sorted_merge(current.next, element)
		end
	end
	# Sorting the linked list elements using recursion
	def sort()
	
		# Base case   
		if (self.head == nil || self.head.next == nil)
		
			# When linked list is empty or only one element
			return
		end
		# Get head element of linked list
		element = self.head
		# Modify the head element of linked list
		self.head = element.next
		# Separate previous head element
		element.next = nil
		# Recursively executing sort process
		self.sort()
		if (element.data <= self.head.data)
		
			# Get a smallest Element
			element.next = self.head
			self.head = element
		else
		
			# Add element in sorted position
			self.sorted_merge(self.head, element)
		end
	end
end
def main()

	obj = MyLinkedList.new()
	# Add element
	obj.insert(16)
	obj.insert(42)
	obj.insert(3)
	obj.insert(22)
	obj.insert(-5)
	obj.insert(8)
	obj.insert(5)
	obj.insert(15)
	print("\n Before Sort : ")
	obj.display()
	obj.sort()
	print("\n After Sort : ")
	obj.display()
end
main()

Output

 Before Sort :   15  5  8  -5  22  3  42  16

 After Sort :   -5  3  5  8  15  16  22  42
// Scala Program 
// Sort linked list using recursion
// Linked List node
class Node(var data: Int,var next: Node)
{}
class MyLinkedList(var head: Node)
{
	//Class constructors LinkedList
	def this()
	{
		this(null);
	}
	//insert newly element
	def insert(data: Int): Unit = {
		//Make a new node of linked list
		var node: Node = new Node(data, this.head);
		if (node != null)
		{
			//Make a new head
			this.head = node;
		}
	}
	//display all Linked List elements
	def display(): Unit = {
		if (head != null)
		{
			var temp: Node = head;
			//iterating Linked List node elements, from the first node to last node
			while (temp != null)
			{
				// Display node values
				print("  " + temp.data);
				// Visit to next node
				temp = temp.next;
			}
			print("\n");
		}
		else
		{
			print("Empty Linked list");
		}
	}
	//This function are add new linked list element in sorted position
	def sorted_merge(current: Node, element: Node): Unit = {
		if (current.next == null)
		{
			//Add element at the end
			current.next = element;
		}
		else if (current.next.data >= element.data)
		{
			element.next = current.next;
			current.next = element;
		}
		else
		{
			sorted_merge(current.next, element);
		}
	}
	//Sorting the linked list elements using recursion
	def sort(): Unit = {
		//Base case   
		if (this.head == null || this.head.next == null)
		{
			//When linked list is empty or only one element
			return;
		}
		//Get head element of linked list
		var element: Node = this.head;
		//Modify the head element of linked list
		this.head = element.next;
		//Separate previous head element
		element.next = null;
		//Recursively executing sort process
		this.sort();
		if (element.data <= this.head.data)
		{
			//Get a smallest Element
			element.next = this.head;
			this.head = element;
		}
		else
		{
			//Add element in sorted position
			sorted_merge(this.head, element);
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyLinkedList = new MyLinkedList();
		//Add element
		obj.insert(16);
		obj.insert(42);
		obj.insert(3);
		obj.insert(22);
		obj.insert(-5);
		obj.insert(8);
		obj.insert(5);
		obj.insert(15);
		print("\n Before Sort : ");
		obj.display();
		obj.sort();
		print("\n After Sort : ");
		obj.display();
	}
}

Output

 Before Sort :   15  5  8  -5  22  3  42  16

 After Sort :   -5  3  5  8  15  16  22  42
// Swift Program 
// Sort linked list using recursion
// Linked List node
class Node
{
	//Define linked list node elements
	var data: Int;
	var next: Node? ;
	init(_ data: Int, _ next_node: Node? )
	{
		//set values of linked list
		self.data = data;
		self.next = next_node;
	}
}
class MyLinkedList
{
	var head: Node? ;
	//Class constructors LinkedList
	init()
	{
		self.head = nil;
	}
	//insert newly element
	func insert(_ data: Int)
	{
		//Make a new node of linked list
		let node: Node? = Node(data, self.head);
		if (node != nil)
		{
			//Make a new head
			self.head = node;
		}
	}
	//display all Linked List elements
	func display()
	{
		if (self.head != nil)
		{
			var temp: Node? = self.head;
			//iterating Linked List node elements, from the first node to last node
			while (temp != nil)
			{
				print("  ", temp!.data, terminator: "");
				// Visit to next node
				temp = temp!.next;
			}
			print("\n", terminator: "");
		}
		else
		{
			print("Empty Linked list", terminator: "");
		}
	}
	//This function are add new linked list element in sorted position
	func sorted_merge(_ current: Node? , _ element : Node? )
	{
		if (current!.next == nil)
		{
			//Add element at the end
			current!.next = element;
		}
		else if (current!.next!.data >= element!.data)
		{
			element!.next = current!.next;
			current!.next = element;
		}
		else
		{
			self.sorted_merge(current!.next, element);
		}
	}
	//Sorting the linked list elements using recursion
	func sort()
	{
		//Base case   
		if (self.head == nil || self.head!.next == nil)
		{
			//When linked list is empty or only one element
			return;
		}
		//Get head element of linked list
		let element: Node? = self.head;
		//Modify the head element of linked list
		self.head = element!.next;
		//Separate previous head element
		element!.next = nil;
		//Recursively executing sort process
		self.sort();
		if (element!.data <= self.head!.data)
		{
			//Get a smallest Element
			element!.next = self.head;
			self.head = element;
		}
		else
		{
			//Add element in sorted position
			self.sorted_merge(self.head, element);
		}
	}
}
func main()
{
	let obj: MyLinkedList = MyLinkedList();
	//Add element
	obj.insert(16);
	obj.insert(42);
	obj.insert(3);
	obj.insert(22);
	obj.insert(-5);
	obj.insert(8);
	obj.insert(5);
	obj.insert(15);
	print("\n Before Sort : ", terminator: "");
	obj.display();
	obj.sort();
	print("\n After Sort : ", terminator: "");
	obj.display();
}
main();

Output

 Before Sort :    15   5   8   -5   22   3   42   16

 After Sort :    -5   3   5   8   15   16   22   42


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







© 2021, kalkicode.com, All rights reserved