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
insert(head, value):
    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
sort(head):
    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
        head = element
    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;
		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

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.

New Comment