« Previous Next »

Reverse linked list using recursion

Here given code implementation process.

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

#include <stdlib.h> //for malloc function

//Structure of linked list node
struct Node
{
	int data;
	struct Node *next;
};
//Add new node at end of linked list
void insert(struct Node **head, int value)
{
	//Create dynamic node
	struct Node *node = (struct Node *) malloc(sizeof(struct Node));
	if (node == NULL)
	{
		printf("Memory overflow\n");
	}
	else
	{
		//Assign data value
		node->data = value;
		node->next = NULL;
		if ( *head == NULL)
		{
			*head = node;
		}
		else
		{
			struct Node *temp = *head;
			//Find last node of linked list
			while (temp->next != NULL)
			{
				temp = temp->next;
			}
			//add node at last possition
			temp->next = node;
		}
	}
}
//Display element of Node
void display(struct Node *temp)
{
	if (temp == NULL)
	{
		printf("Empty linked list");
	}
	while (temp != NULL)
	{
		printf("%d  ", temp->data);
		temp = temp->next;
	}
}
//Reverse linked list node
void reverse_nodes(struct Node **head)
{
	//Base case when need to stop recursion
	if ( *head == NULL)
	{
		return;
	}
	//Variable which is hold information of 
	//current and next node of linked list
	struct Node *current_node = *head;
	struct Node *next_node = NULL;
	if (current_node->next != NULL)
	{
		//When next node exist in linked list
		next_node = current_node->next;
	}
	if ( *head != NULL)
	{
		//Set new head node
		*head = next_node;
		reverse_nodes(head);
	}
	if (next_node == NULL)
	{
		//When get a last node of linked list
		*head = current_node;
	}
	if (next_node != NULL)
	{
		//When need to combining of next node linked to previous node
		next_node->next = current_node;
	}
	//Unlink previous exist connection
	current_node->next = NULL;
}
int main()
{
	//create node pointer
	struct Node *head = NULL;
	//Add elements in linked list
	insert( & head, 1);
	insert( & head, 4);
	insert( & head, 3);
	insert( & head, 7);
	insert( & head, 8);
	printf("\n Before Reverse : ");
	display(head);
	reverse_nodes( & head);
	printf("\n After  Reverse : ");
	display(head);
	return 0;
}

Output

 Before Reverse : 1  4  3  7  8
 After  Reverse : 8  7  3  4  1

//Java Program
//Reverse linked list using recursion
class Node
{
	public int data;
	public Node next;
	//Make a new node
	public Node(int data)
	{
		this.data = data;
		this.next = null;
	}
}
class MyLinkedList
{
	public Node head;
	public Node tail;
	//Class constructors
	public MyLinkedList()
	{
		this.head = null;
		this.tail = null;
	}
	//Add new node at end of linked list
	public void insert(int data)
	{
		//Create  node
		Node new_node = new Node(data);
		if (this.head == null)
		{
			this.head = new_node;
			this.tail = new_node;
		}
		else
		{
			this.tail.next = new_node;
			this.tail = new_node;
		}
	}
	//Display element of Node
	public void display()
	{
		Node temp = this.head;
		if (temp == null)
		{
			System.out.print("Empty linked list");
		}
		while (temp != null)
		{
			System.out.print(" " + temp.data);
			temp = temp.next;
		}
	}
	//Reverse linked list node
	public void reverse_nodes()
	{
		//Base case when need to stop recursion
		if (this.head == null)
		{
			return;
		}
		//Variable which is hold information of 
		//current and next node of linked list
		Node current_node = this.head;
		Node next_node = null;
		if (current_node.next != null)
		{
			//When next node exist in linked list
			next_node = current_node.next;
		}
		if (this.head != null)
		{
			//Set new head node
			this.head = next_node;
			reverse_nodes();
		}
		if (next_node == null)
		{
			//When get a last node of linked list
			this.head = current_node;
			this.tail = current_node;
		}
		//Unlink previous exist connection
		current_node.next = null;
		this.tail.next = current_node;
		this.tail = current_node;
	}
	public static void main(String[] args)
	{
		MyLinkedList obj = new MyLinkedList();
		//Add elements in linked list
		obj.insert(1);
		obj.insert(4);
		obj.insert(3);
		obj.insert(7);
		obj.insert(8);
		System.out.print("\n Before Reverse : ");
		obj.display();
		obj.reverse_nodes();
		System.out.print("\n After  Reverse : ");
		obj.display();
	}
}

Output

 Before Reverse :  1 4 3 7 8
 After  Reverse :  8 7 3 4 1

//Include header file
#include <iostream>
using namespace std;

//C++ Program
//Reverse linked list using recursion
class Node
{
	public: int data;
	Node * next;
	//Make a new node
	Node(int data)
	{
		this->data = data;
		this->next = NULL;
	}
};
class MyLinkedList
{
	public: Node * head;
	Node * tail;
	//Class constructors
	MyLinkedList()
	{
		this->head = NULL;
		this->tail = NULL;
	}
	//Add new node at end of linked list
	void insert(int data)
	{
		//Create  node
		Node * new_node = new Node(data);
		if (this->head == NULL)
		{
			this->head = new_node;
			this->tail = new_node;
		}
		else
		{
			this->tail->next = new_node;
			this->tail = new_node;
		}
	}
	//Display element of Node
	void display()
	{
		Node * temp = this->head;
		if (temp == NULL)
		{
			cout << "Empty linked list";
		}
		while (temp != NULL)
		{
			cout << " " << temp->data;
			temp = temp->next;
		}
	}
	//Reverse linked list node
	void reverse_nodes()
	{
		//Base case when need to stop recursion
		if (this->head == NULL)
		{
			return;
		}
		//Variable which is hold information of 
		//current and next node of linked list
		Node * current_node = this->head;
		Node * next_node = NULL;
		if (current_node->next != NULL)
		{
			//When next node exist in linked list
			next_node = current_node->next;
		}
		if (this->head != NULL)
		{
			//Set new head node
			this->head = next_node;
			this->reverse_nodes();
		}
		if (next_node == NULL)
		{
			//When get a last node of linked list
			this->head = current_node;
			this->tail = current_node;
		}
		//Unlink previous exist connection
		current_node->next = NULL;
		this->tail->next = current_node;
		this->tail = current_node;
	}
};
int main()
{
	MyLinkedList obj = MyLinkedList();
	//Add elements in linked list
	obj.insert(1);
	obj.insert(4);
	obj.insert(3);
	obj.insert(7);
	obj.insert(8);
	cout << "\n Before Reverse : ";
	obj.display();
	obj.reverse_nodes();
	cout << "\n After  Reverse : ";
	obj.display();
	return 0;
}

Output

 Before Reverse : 1  4  3  7  8
 After  Reverse : 8  7  3  4  1

//Include namespace system
using System;
//C# Program
//Reverse linked list using recursion
class Node
{
	public int data;
	public Node next;
	//Make a new node
	public Node(int data)
	{
		this.data = data;
		this.next = null;
	}
}
class MyLinkedList
{
	public Node head;
	public Node tail;
	//Class constructors
	public MyLinkedList()
	{
		this.head = null;
		this.tail = null;
	}
	//Add new node at end of linked list
	public void insert(int data)
	{
		//Create  node
		Node new_node = new Node(data);
		if (this.head == null)
		{
			this.head = new_node;
			this.tail = new_node;
		}
		else
		{
			this.tail.next = new_node;
			this.tail = new_node;
		}
	}
	//Display element of Node
	public void display()
	{
		Node temp = this.head;
		if (temp == null)
		{
			Console.Write("Empty linked list");
		}
		while (temp != null)
		{
			Console.Write(" " + temp.data);
			temp = temp.next;
		}
	}
	//Reverse linked list node
	public void reverse_nodes()
	{
		//Base case when need to stop recursion
		if (this.head == null)
		{
			return;
		}
		//Variable which is hold information of 
		//current and next node of linked list
		Node current_node = this.head;
		Node next_node = null;
		if (current_node.next != null)
		{
			//When next node exist in linked list
			next_node = current_node.next;
		}
		if (this.head != null)
		{
			//Set new head node
			this.head = next_node;
			reverse_nodes();
		}
		if (next_node == null)
		{
			//When get a last node of linked list
			this.head = current_node;
			this.tail = current_node;
		}
		//Unlink previous exist connection
		current_node.next = null;
		this.tail.next = current_node;
		this.tail = current_node;
	}
	public static void Main(String[] args)
	{
		MyLinkedList obj = new MyLinkedList();
		//Add elements in linked list
		obj.insert(1);
		obj.insert(4);
		obj.insert(3);
		obj.insert(7);
		obj.insert(8);
		Console.Write("\n Before Reverse : ");
		obj.display();
		obj.reverse_nodes();
		Console.Write("\n After  Reverse : ");
		obj.display();
	}
}

Output

 Before Reverse :  1 4 3 7 8
 After  Reverse :  8 7 3 4 1

<?php
//Php Program
//Reverse linked list using recursion
class Node
{
	public $data;
	public $next;
	//Make a new node
	function __construct($data)
	{
		$this->data = $data;
		$this->next = null;
	}
}
class MyLinkedList
{
	public $head;
	public $tail;
	//Class constructors
	function __construct()
	{
		$this->head = null;
		$this->tail = null;
	}
	//Add new node at end of linked list
	public	function insert($data)
	{
		//Create  node
		$new_node = new Node($data);
		if ($this->head == null)
		{
			$this->head = $new_node;
			$this->tail = $new_node;
		}
		else
		{
			$this->tail->next = $new_node;
			$this->tail = $new_node;
		}
	}
	//Display element of Node
	public	function display()
	{
		$temp = $this->head;
		if ($temp == null)
		{
			echo "Empty linked list";
		}
		while ($temp != null)
		{
			echo " ". $temp->data;
			$temp = $temp->next;
		}
	}
	//Reverse linked list node
	public	function reverse_nodes()
	{
		//Base case when need to stop recursion
		if ($this->head == null)
		{
			return;
		}
		//Variable which is hold information of 
		//current and next node of linked list
		$current_node = $this->head;
		$next_node = null;
		if ($current_node->next != null)
		{
			//When next node exist in linked list
			$next_node = $current_node->next;
		}
		if ($this->head != null)
		{
			//Set new head node
			$this->head = $next_node;
			$this->reverse_nodes();
		}
		if ($next_node == null)
		{
			//When get a last node of linked list
			$this->head = $current_node;
			$this->tail = $current_node;
		}
		//Unlink previous exist connection
		$current_node->next = null;
		$this->tail->next = $current_node;
		$this->tail = $current_node;
	}
}

function main()
{
	$obj = new MyLinkedList();
	//Add elements in linked list
	$obj->insert(1);
	$obj->insert(4);
	$obj->insert(3);
	$obj->insert(7);
	$obj->insert(8);
	echo "\n Before Reverse : ";
	$obj->display();
	$obj->reverse_nodes();
	echo "\n After  Reverse : ";
	$obj->display();
}
main();

Output

 Before Reverse :  1 4 3 7 8
 After  Reverse :  8 7 3 4 1

//Node Js Program
//Reverse linked list using recursion
class Node
{
	//Make a new node
	constructor(data)
	{
		this.data = data;
		this.next = null;
	}
}
class MyLinkedList
{
	//Class constructors
	constructor()
	{
		this.head = null;
		this.tail = null;
	}
	//Add new node at end of linked list
	insert(data)
	{
		//Create  node
		var new_node = new Node(data);
		if (this.head == null)
		{
			this.head = new_node;
			this.tail = new_node;
		}
		else
		{
			this.tail.next = new_node;
			this.tail = new_node;
		}
	}
	//Display element of Node
	display()
	{
		var temp = this.head;
		if (temp == null)
		{
			process.stdout.write("Empty linked list");
		}
		while (temp != null)
		{
			process.stdout.write(" " + temp.data);
			temp = temp.next;
		}
	}
	//Reverse linked list node
	reverse_nodes()
	{
		//Base case when need to stop recursion
		if (this.head == null)
		{
			return;
		}
		//Variable which is hold information of 
		//current and next node of linked list
		var current_node = this.head;
		var next_node = null;
		if (current_node.next != null)
		{
			//When next node exist in linked list
			next_node = current_node.next;
		}
		if (this.head != null)
		{
			//Set new head node
			this.head = next_node;
			this.reverse_nodes();
		}
		if (next_node == null)
		{
			//When get a last node of linked list
			this.head = current_node;
			this.tail = current_node;
		}
		//Unlink previous exist connection
		current_node.next = null;
		this.tail.next = current_node;
		this.tail = current_node;
	}
}

function main()
{
	var obj = new MyLinkedList();
	//Add elements in linked list
	obj.insert(1);
	obj.insert(4);
	obj.insert(3);
	obj.insert(7);
	obj.insert(8);
	process.stdout.write("\n Before Reverse : ");
	obj.display();
	obj.reverse_nodes();
	process.stdout.write("\n After  Reverse : ");
	obj.display();
}
main();

Output

 Before Reverse :  1 4 3 7 8
 After  Reverse :  8 7 3 4 1

# Python 3 Program
# Reverse linked list using recursion
class Node :
	
	# Make a new node
	def __init__(self, data) :
		self.data = data
		self.next = None
	

class MyLinkedList :
	
	# Class constructors
	def __init__(self) :
		self.head = None
		self.tail = None
	
	# Add new node at end of linked list
	def insert(self, data) :
		# Create  node
		new_node = Node(data)
		if (self.head == None) :
			self.head = new_node
			self.tail = new_node
		else :
			self.tail.next = new_node
			self.tail = new_node
		
	
	# Display element of Node
	def display(self) :
		temp = self.head
		if (temp == None) :
			print("Empty linked list", end = "")
		
		while (temp != None) :
			print(" ", temp.data, end = "")
			temp = temp.next
		
	
	# Reverse linked list node
	def reverse_nodes(self) :
		# Base case when need to stop recursion
		if (self.head == None) :
			return
		
		# Variable which is hold information of 
		# current and next node of linked list
		current_node = self.head
		next_node = None
		if (current_node.next != None) :
			# When next node exist in linked list
			next_node = current_node.next
		
		if (self.head != None) :
			# Set new head node
			self.head = next_node
			self.reverse_nodes()
		
		if (next_node == None) :
			# When get a last node of linked list
			self.head = current_node
			self.tail = current_node
		
		# Unlink previous exist connection
		current_node.next = None
		self.tail.next = current_node
		self.tail = current_node
	

def main() :
	obj = MyLinkedList()
	# Add elements in linked list
	obj.insert(1)
	obj.insert(4)
	obj.insert(3)
	obj.insert(7)
	obj.insert(8)
	print("\n Before Reverse : ", end = "")
	obj.display()
	obj.reverse_nodes()
	print("\n After  Reverse : ", end = "")
	obj.display()

if __name__ == "__main__": main()

Output

 Before Reverse :   1  4  3  7  8
 After  Reverse :   8  7  3  4  1

# Ruby Program
# Reverse linked list using recursion
class Node 

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

	# Make a new node
	def initialize(data)
	
		self.data = data
		self.next = nil
	end
end
class MyLinkedList 

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


	# Class constructors
	def initialize()
	
		self.head = nil
		self.tail = nil
	end
	# Add new node at end of linked list
	def insert(data)
	
		# Create  node
		new_node = Node.new(data)
		if (self.head == nil)
		
			self.head = new_node
			self.tail = new_node
		else
		
			self.tail.next = new_node
			self.tail = new_node
		end
	end
	# Display element of Node
	def display()
	
		temp = self.head
		if (temp == nil)
		
			print("Empty linked list")
		end
		while (temp != nil)
		
			print(" ", temp.data)
			temp = temp.next
		end
	end
	# Reverse linked list node
	def reverse_nodes()
	
		# Base case when need to stop recursion
		if (self.head == nil)
		
			return
		end
		# Variable which is hold information of 
		# current and next node of linked list
		current_node = self.head
		next_node = nil
		if (current_node.next != nil)
		
			# When next node exist in linked list
			next_node = current_node.next
		end
		if (self.head != nil)
		
			# Set new head node
			self.head = next_node
			self.reverse_nodes()
		end
		if (next_node == nil)
		
			# When get a last node of linked list
			self.head = current_node
			self.tail = current_node
		end
		# Unlink previous exist connection
		current_node.next = nil
		self.tail.next = current_node
		self.tail = current_node
	end
end
def main()

	obj = MyLinkedList.new()
	# Add elements in linked list
	obj.insert(1)
	obj.insert(4)
	obj.insert(3)
	obj.insert(7)
	obj.insert(8)
	print("\n Before Reverse : ")
	obj.display()
	obj.reverse_nodes()
	print("\n After  Reverse : ")
	obj.display()
end
main()

Output

 Before Reverse :  1 4 3 7 8
 After  Reverse :  8 7 3 4 1

//Scala Program
//Reverse linked list using recursion
class Node(var data: Int,
	var next: Node)
{
	//Make a new node
	def this(data: Int)
	{
		this(data, null);
	}
}
class MyLinkedList(var head: Node,
	var tail: Node)
{
	//Class constructors
	def this()
	{
		this(null, null);
	}
	//Add new node at end of linked list
	def insert(data: Int): Unit = {
		//Create  node
		var new_node: Node = new Node(data);
		if (this.head == null)
		{
			this.head = new_node;
			this.tail = new_node;
		}
		else
		{
			this.tail.next = new_node;
			this.tail = new_node;
		}
	}
	//Display element of Node
	def display(): Unit = {
		var temp: Node = this.head;
		if (temp == null)
		{
			print("Empty linked list");
		}
		while (temp != null)
		{
			print(" " + temp.data);
			temp = temp.next;
		}
	}
	//Reverse linked list node
	def reverse_nodes(): Unit = {
		//Base case when need to stop recursion
		if (this.head == null)
		{
			return;
		}
		//Variable which is hold information of 
		//current and next node of linked list
		var current_node: Node = this.head;
		var next_node: Node = null;
		if (current_node.next != null)
		{
			//When next node exist in linked list
			next_node = current_node.next;
		}
		if (this.head != null)
		{
			//Set new head node
			this.head = next_node;
			reverse_nodes();
		}
		if (next_node == null)
		{
			//When get a last node of linked list
			this.head = current_node;
			this.tail = current_node;
		}
		//Unlink previous exist connection
		current_node.next = null;
		this.tail.next = current_node;
		this.tail = current_node;
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyLinkedList = new MyLinkedList();
		//Add elements in linked list
		obj.insert(1);
		obj.insert(4);
		obj.insert(3);
		obj.insert(7);
		obj.insert(8);
		print("\n Before Reverse : ");
		obj.display();
		obj.reverse_nodes();
		print("\n After  Reverse : ");
		obj.display();
	}
}

Output

 Before Reverse :  1 4 3 7 8
 After  Reverse :  8 7 3 4 1

//Swift Program
//Reverse linked list using recursion
class Node
{
	var data: Int;
	var next: Node? ;
	//Make a new node
	init(_ data: Int)
	{
		self.data = data;
		self.next = nil;
	}
}
class MyLinkedList
{
	var head: Node? ;
	var tail: Node? ;
	//Class constructors
	init()
	{
		self.head = nil;
		self.tail = nil;
	}
	//Add new node at end of linked list
	func insert(_ data: Int)
	{
		//Create  node
		let new_node: Node? = Node(data);
		if (self.head == nil)
		{
			self.head = new_node;
			self.tail = new_node;
		}
		else
		{
			self.tail!.next = new_node;
			self.tail = new_node;
		}
	}
	//Display element of Node
	func display()
	{
		var temp: Node? = self.head;
		if (temp == nil)
		{
			print("Empty linked list", terminator: "");
		}
		while (temp != nil)
		{
			print(" ", temp!.data, terminator: "");
			temp = temp!.next;
		}
	}
	//Reverse linked list node
	func reverse_nodes()
	{
		//Base case when need to stop recursion
		if (self.head == nil)
		{
			return;
		}
		//Variable which is hold information of 
		//current and next node of linked list
		let current_node: Node? = self.head;
		var next_node: Node? = nil;
		if (current_node!.next != nil)
		{
			//When next node exist in linked list
			next_node = current_node!.next;
		}
		if (self.head != nil)
		{
			//Set new head node
			self.head = next_node;
			self.reverse_nodes();
		}
		if (next_node == nil)
		{
			//When get a last node of linked list
			self.head = current_node;
			self.tail = current_node;
		}
		//Unlink previous exist connection
		current_node!.next = nil;
		self.tail!.next = current_node;
		self.tail = current_node;
	}
}
func main()
{
	let obj: MyLinkedList = MyLinkedList();
	//Add elements in linked list
	obj.insert(1);
	obj.insert(4);
	obj.insert(3);
	obj.insert(7);
	obj.insert(8);
	print("\n Before Reverse : ", terminator: "");
	obj.display();
	obj.reverse_nodes();
	print("\n After  Reverse : ", terminator: "");
	obj.display();
}
main();

Output

 Before Reverse :   1  4  3  7  8
 After  Reverse :   8  7  3  4  1

« Previous Next »

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.