Posted on by Kalkicode
Code Recursion

# Sort linked list using recursion

In this article, we will explore the problem of sorting a linked list using recursion. A linked list is a data structure composed of nodes where each node contains a data element and a reference (or pointer) to the next node in the sequence. The goal of this problem is to rearrange the elements in the linked list in ascending order.

## Problem Statement

The problem can be defined as follows: Given a singly linked list, we need to sort its elements in ascending order using a recursive approach. The linked list can have any number of elements, and we want to modify it in-place, without creating a new linked list.

## Explanation with Suitable Example

Let's take an example to illustrate the problem. Consider a linked list with the following elements: 15 -> 5 -> 8 -> -5 -> 22 -> 3 -> 42 -> 16. Our goal is to sort this linked list in ascending order using recursion.

## Pseudocode

Below is the pseudocode for sorting the linked list using recursion:

``````# Structure of a Node in the linked list
Node:
data     # data element of the node
next     # reference to the next node in the linked list

# Function to insert a new node at the beginning of the linked list
node = new Node   # Create a new node
node.data = value # Set the data of the node to the given value
node.next = head  # Make the new node point to the current head
head = node       # Make the new node the new head of the list

# Function to merge an element into the sorted linked list
sorted_merge(current, element):
if current.next == NULL:
current.next = element    # Add the element at the end of the list
if current.next.data >= element.data:
element.next = current.next
current.next = element    # Insert the element before the next node
if current.next.data < element.data:
sorted_merge(current.next, element)   # Recursively merge with the next node

# Function to sort the linked list using recursion
if head == NULL or head.next == NULL:
return   # Base case: list is empty or has only one element

element = head       # Store the current head as the element to be sorted
head = element.next  # Move the head to the next element
element.next = NULL  # Separate the element from the rest of the list

sort(head)    # Recursively sort the remaining list

if element.data <= head.data:
element.next = head   # Element becomes the new head
if element.data > head.data:
sorted_merge(head, element)   # Insert the element in the sorted position
``````

## Algorithm Explanation

1. The `sorted_merge` function takes two linked list nodes `current` and `element` as input. It compares the data of `element` with the next node pointed by `current`. If the next node is NULL, it adds `element` at the end. If the data in the next node is greater than or equal to the data in `element`, it inserts `element` before the next node. Otherwise, it recursively calls `sorted_merge` with the next node.

2. The `sort` function takes a pointer to the head of the linked list as input. It serves as our main sorting function using recursion. The base case checks if the linked list is empty or has only one element. If so, the function returns.

3. If the base case is not reached, it takes the head element of the linked list and separates it from the rest of the list by updating the head to the next element.

4. The function then recursively calls `sort` with the updated head.

5. After the recursive call, it compares the data of the separated element with the data of the new head. If the data of the element is less than or equal to the data of the new head, it becomes the new head. Otherwise, it calls `sorted_merge` to insert the element in the sorted position.

## Program Solution

``````// 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;
}
}
//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;
}
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
if (element->data <= ( *head)->data)
{
//Get a smallest Element
}
else
{
//Add element in sorted position
}
}
//Display element of Node
void display(struct Node *head)
{
while (head != NULL)
{
}
}
int main()
{
struct Node *head = NULL;
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 : ");
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
// 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;
}
}
{
{
}
//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
}
}
//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
{
}
}
//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;
}
Node element = this.head;
//Modify the head element of linked list
//Separate previous head element
element.next = null;
//Recursively executing sort process
this.sort();
if (element.data <= this.head.data)
{
//Get a smallest Element
}
else
{
//Add element in sorted position
}
}
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
// 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;
}
};
{
public: Node * head;
{
}
//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
}
}
//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;
}
Node * element = this->head;
//Modify the head element of linked list
//Separate previous head element
element->next = NULL;
//Recursively executing sort process
this->sort();
if (element->data <= this->head->data)
{
//Get a smallest Element
}
else
{
//Add element in sorted position
}
}
};
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
// 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;
}
}
{
{
}
//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
}
}
//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
{
}
}
//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;
}
Node element = this.head;
//Modify the head element of linked list
//Separate previous head element
element.next = null;
//Recursively executing sort process
this.sort();
if (element.data <= this.head.data)
{
//Get a smallest Element
}
else
{
//Add element in sorted position
}
}
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
// 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;
}
}
{
function __construct()
{
}
//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
}
}
//display all Linked List elements
public	function display()
{
if (\$this->head != null)
{
//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;
}
//Modify the head element of linked list
//Separate previous head element
\$element->next = null;
//Recursively executing sort process
\$this->sort();
if (\$element->data <= \$this->head->data)
{
//Get a smallest Element
}
else
{
//Add element in sorted position
}
}
}

function main()
{
\$obj = new MyLinkedList();
\$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;
}
}
{
constructor()
{
}
//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
}
}
//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
{
}
}
//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;
}
var element = this.head;
//Modify the head element of linked list
//Separate previous head element
element.next = null;
//Recursively executing sort process
this.sort();
if (element.data <= this.head.data)
{
//Get a smallest Element
}
else
{
//Add element in sorted position
}
}
}

function main()
{
var obj = new MyLinkedList();
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 constructors LinkedList
def __init__(self) :

# 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

# display all Linked List elements
def display(self) :
if (self.head != None) :
# 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
# Modify the head element of linked list
# Separate previous head element
element.next = None
# Recursively executing sort process
self.sort()
if (element.data <= self.head.data) :
# 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

#  Linked List node
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

# Define the accessor and reader of class MyLinkedList

# Class constructors LinkedList
def initialize()
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
end
end
# display all Linked List elements
def display()

if (@head != nil)

# 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
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
# Modify the head element of linked list
# Separate previous head element
element.next = nil
# Recursively executing sort process
self.sort()
if (element.data <= self.head.data)

# 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
// Linked List node
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)
{
//Make a new head
}
}
//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
{
}
}
//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;
}
var element: Node = this.head;
//Modify the head element of linked list
//Separate previous head element
element.next = null;
//Recursively executing sort process
this.sort();
if (element.data <= this.head.data)
{
//Get a smallest Element
}
else
{
//Add element in sorted position
}
}
}
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
// 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;
}
}
{
var head: 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)
{
//Make a new head
}
}
//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;
}
let element: Node? = self.head;
//Modify the head element of linked list
//Separate previous head element
element!.next = nil;
//Recursively executing sort process
self.sort();
if (element!.data <= self.head!.data)
{
//Get a smallest Element
}
else
{
//Add element in sorted position
}
}
}
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``````

## Resultant Output Explanation

Using the example linked list (15 -> 5 -> 8 -> -5 -> 22 -> 3 -> 42 -> 16), the output after sorting will be: -5 -> 3 -> 5 -> 8 -> 15 -> 16 -> 22 -> 42.

## Time Complexity

The time complexity of this algorithm can be analyzed as follows:

• The `sorted_merge` function inserts an element in the linked list at the correct position, which takes O(1) time in the best and average cases. However, in the worst case, when the element to be inserted is greater than all existing elements, it may take O(n) time, where n is the number of elements in the linked list.
• The `sort` function recursively divides the linked list into smaller parts until reaching the base case. Since each call reduces the size of the list by one element, the time complexity of this step is O(n) in the worst case.
• Combining both steps, the overall time complexity of sorting the linked list using recursion is O(n^2) in the worst case.

Finally, this article has discussed the problem of sorting a linked list using recursion. It presented a detailed explanation of the problem, provided pseudocode and an algorithm for sorting the linked list, and explained the output after sorting. The time complexity of the algorithm was also analyzed, highlighting the potential performance trade-offs. Sorting linked lists with recursion can be a useful technique when an iterative approach is not desired or when recursion fits the problem domain better.

## Comment

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

Categories
Relative Post