Home » Interview Questions » LinkedList Interview Questions » Reverse a singly linked list recursively

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;
}

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions