Reverse a Linked List using Recursion in C++ [New]

 In this program, we will reverse a linked list using recursion. Whenever you solve a problem using recursion, then please think about the following things:

1. Base Case: It is an essential step for recursion. Without this statement, your code will not stop, and the compiler will give segmentation fault. To write a base case, you must consider the smallest valid input.


2. Induction Hypothesis: Induction Hypothesis: Call your recursive function and assume it will perform its operation. For reverse(head->next), it will reverse the linked list from the next node and return the new head of the reversed link list.


3. Induction Step: In this step, we write the logic of our recursive function. In short, we decide on this step.
   
   
   
   

Pre-requisite: Linked Lists Data Structure in C++

Reverse a Linked List using Recursion in C++

In this program, our base case is when the linked list has only one node. In this case, we have to return that node. Then, we call our recursive function to reverse the remaining linked list.

At the decision step, the Next node of the head should point to our current head node. Our current node will point to NULL. At last, we return that node we get from our recursive function.

node * reverseRecursion(node * head)
{
    if(head->next==NULL)
    return head;
    node * temp=reverseRecursion(head->next);
    head->next->next=head;
    head->next=NULL;
    return temp;
}

Output:

Before: 1->2->3->4->5->6
After: 6->5->4->3->2->1

Video Solution for Reversing linked list recursively

C++ Program to reverse a linked list

In this example, we create a linked list from an array. The following program consists of the following functions:

• Create: This function makes a linked list from the given array.
• Display: It is used to print our linked list.
• Reverse: In this function, we reverse the linked list and return the tail of the linked list.

#include <bits/stdc++.h>
using namespace std;
struct node
{
	int data;
	node* next;
}*first,*last;
void create(int arr[],int n)
{
	int i;
	node *t,*last;
	first = new node();
	first->data=arr[0];
	first->next=NULL;
	last=first;
	for(i=1;i<n;i++)
	{
		t=new node();
		t->data=arr[i];
		t->next=NULL;
		last->next=t;
		last=t;
	}
}
void display(node *head)
{
 while(head->next!=NULL)
 {
 cout<<head->data<<"->";
 head=head->next;
 }
 cout<<head->data<<endl;
}

void reverse(node * &head)
{
	node *r=NULL,*q=NULL,*p=head;
	while(p)
	{
		r=q;
		q=p;
		p=p->next;
		q->next=r;
	}
	head=q;
}

node * reverseRecursion(node * head)
{
    if(head->next==NULL)
    return head;
    node * temp=reverseRecursion(head->next);
    head->next->next=head;
    head->next=NULL;
    return temp;
}


int main()
{
	int arr[]={1,2,3,4,5,6};
	int n=sizeof(arr)/sizeof(int);
	create(arr,n);
	display(first);
    first=reverseRecursion(first);
    display(first);
	return 0;
}

About this Program

In conclusion, we reversed a Linked List using recursion in c++. Ask your doubts in the comment section. Your feedbacks are significant for us; please tell us how we can improve in the comment section.