# 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;
}
}
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
{
//Base case
{
//When linked list is empty or only one element
return;
}
struct Node *element = ( *head);
element->next = NULL;
//Recursively executing sort process
{
//Get a smallest Element
}
else
{
}
}
//Display element of Node
{
{
}
}
int main()
{
printf("\n Before Sort : ");
printf("\n After Sort : ");
}``````

#### 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
class Node
{
public int data;
public Node next;
public Node(int data, Node next_node)
{
this.data = data;
this.next = next_node;
}
}
{
{
}
//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)
{
}
}
public void display()
{
{
//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
{
}
}
public void sorted_merge(Node current, Node element)
{
if (current.next == null)
{
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
{
//When linked list is empty or only one element
return;
}
element.next = null;
//Recursively executing sort process
this.sort();
{
//Get a smallest Element
}
else
{
}
}
public static void main(String[] args)
{
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
class Node
{
public:
int data;
Node * next;
Node(int data, Node * next_node)
{
this->data = data;
this->next = next_node;
}
};
{
{
}
//insert newly element
void insert(int data)
{
//Make a new node of linked list
Node * node = new Node(data, this->head);
if (node != NULL)
{
}
}
void display()
{
{
//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
{
}
}
void sorted_merge(Node * current, Node * element)
{
if (current->next == NULL)
{
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
{
//When linked list is empty or only one element
return;
}
element->next = NULL;
//Recursively executing sort process
this->sort();
{
//Get a smallest Element
}
else
{
}
}
};
int main()
{
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
class Node
{
public int data;
public Node next;
public Node(int data, Node next_node)
{
this.data = data;
this.next = next_node;
}
}
{
{
}
//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)
{
}
}
public void display()
{
{
//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
{
}
}
public void sorted_merge(Node current, Node element)
{
if (current.next == null)
{
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
{
//When linked list is empty or only one element
return;
}
element.next = null;
//Recursively executing sort process
this.sort();
{
//Get a smallest Element
}
else
{
}
}
public static void Main(String[] args)
{
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
class Node
{
public \$data;
public \$next;

function __construct(\$data, \$next_node)
{
\$this->data = \$data;
\$this->next = \$next_node;
}
}
{
function __construct()
{
}
//insert newly element
public	function insert(\$data)
{
//Make a new node of linked list
if (\$node != null)
{
}
}
public	function display()
{
{
//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
{
}
}
public	function sorted_merge(\$current, \$element)
{
if (\$current->next == null)
{
\$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
{
//When linked list is empty or only one element
return;
}
\$element->next = null;
//Recursively executing sort process
\$this->sort();
{
//Get a smallest Element
}
else
{
}
}
}

function main()
{
\$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
class Node
{
constructor(data, next_node)
{
this.data = data;
this.next = next_node;
}
}
{
constructor()
{
}
//insert newly element
insert(data)
{
//Make a new node of linked list
var node = new Node(data, this.head);
if (node != null)
{
}
}
display()
{
{
//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
{
}
}
sorted_merge(current, element)
{
if (current.next == null)
{
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
{
//When linked list is empty or only one element
return;
}
element.next = null;
//Recursively executing sort process
this.sort();
{
//Get a smallest Element
}
else
{
}
}
}

function main()
{
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

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

def __init__(self) :

# insert newly element
def insert(self, data) :
# Make a new node of linked list
if (node != None) :

# display all Linked List elements
def display(self) :
# 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
# When linked list is empty or only one element
return

element.next = None
# Recursively executing sort process
self.sort()
# Get a smallest Element
else :
# Add element in sorted position

def main() :
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

class Node

# Define the accessor and reader of class Node
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

def initialize()
end
# insert newly element
def insert(data)

# Make a new node of linked list
if (node != nil)

end
end
# display all Linked List elements
def display()

# 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

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

# When linked list is empty or only one element
return
end
element.next = nil
# Recursively executing sort process
self.sort()

# Get a smallest Element
else

# Add element in sorted position
end
end
end
def main()

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
class Node(var data: Int,var next: Node)
{}
{
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)
{
}
}
def display(): Unit = {
{
//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
{
}
}
def sorted_merge(current: Node, element: Node): Unit = {
if (current.next == null)
{
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
{
//When linked list is empty or only one element
return;
}
element.next = null;
//Recursively executing sort process
this.sort();
{
//Get a smallest Element
}
else
{
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
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
class Node
{
var data: Int;
var next: Node? ;
init(_ data: Int, _ next_node: Node? )
{
self.data = data;
self.next = next_node;
}
}
{
init()
{
}
//insert newly element
func insert(_ data: Int)
{
//Make a new node of linked list
let node: Node? = Node(data, self.head);
if (node != nil)
{
}
}
func display()
{
{
//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
{
}
}
func sorted_merge(_ current: Node? , _ element : Node? )
{
if (current!.next == nil)
{
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
{
//When linked list is empty or only one element
return;
}
element!.next = nil;
//Recursively executing sort process
self.sort();
{
//Get a smallest Element
}
else
{
}
}
}
func main()
{
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``````

## 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.