Reverse a singly linked list recursively

Reverse the given singly linked list recursively

Example

Algorithm

Step 1 : create a function that takes a linked list as argument and reverses it.
Step 2 : In the function,
a)    if it is single node or null node just make it as head and return it.
b)    Recursively traverse up end leaving first making the next node to point itself, hence reversing the links.
Step 3 : make next of first node to be Null, which makes it as last node.
Step 4 : call the function on the given Linked list to reverse it.

Algorithm working

C++ Program

#include <bits/stdc++.h>
using namespace std;

struct LL{
	int data;
	LL *next;	
};


void insertAtBeginning(struct LL**head,int dataToBeInserted)
{
	struct LL* curr=new LL;
		
		curr->data=dataToBeInserted;
		curr->next=NULL;
	
	if(*head==NULL)
			*head=curr; //if this is first node make this as head of list
		
	else
		{
			curr->next=*head; //else make the current (new) node's next point to head and make this new node a the head
			*head=curr;
		}
		
		//O(1) constant time
}

void reverseListRecursively(struct LL *root,struct LL**head)
{
	if(root->next==NULL) //if this is the only node make it head and return
		{
			*head=root;
			return;
		}
	
	else
		{
		reverseListRecursively(root->next,head); //traverse upto end first
		root->next->next=root;  //Make the next node to point itself , hence reversing the links
		root->next=NULL;
		}
	//O(2*number of nodes)
	
}
void display(struct LL**head)
{
	struct LL*temp=*head;
	while(temp!=NULL)
		{
			if(temp->next!=NULL)
			cout<<temp->data<<" ->";
			else
			cout<<temp->data;
			
			temp=temp->next; //move to next node
		}
		//O(number of nodes)
	cout<<endl;
}


int main()
{
	
	struct LL *head = NULL; //initial list has no elements
	insertAtBeginning(&head,6);
	insertAtBeginning(&head,16);
	insertAtBeginning(&head,15);
	insertAtBeginning(&head,50);
	insertAtBeginning(&head,1);
	insertAtBeginning(&head,23);
	
	cout<<"Initial List is :-\n";
	display(&head);
	
	reverseListRecursively(head,&head);
	
	cout<<"\nAfter the reverse function the list is :- \n";
	display(&head);
	
	
	return 0;
}

Translate »