Reverse a Linked List recursively

Urwashi Priya
Last Updated: May 13, 2022
Difficulty Level :
EASY

Introduction

In this blog, we will discuss a linked list problem that has been asked frequently in Interviews.

The problem is to Recursively reverse a Linked List which is again an important problem of LinkedList data structure.

So here I am, starting with what is a linked list?

It is an ordered set of elements, each holding data and link containing the address to the next element.

To know more about the linked list, refer here: Linked list 

Now, coming to the question.

Problem Statement

We are given N elements in a linked list, and we are asked to reverse the elements of a linked list by using recursion.

Sample Example

Example:

 

Recommended: Before stepping toward the solution, try it by yourself on CodeStudio.

Approach

Now we will discuss the approach to reverse a linked list recursively.

Declare the Node structure and write the function to insert a node at the tail so that our linked list becomes ready.

Now to recursively reverse the linked list, first write the base condition, i.e., if only one node or no node exists.

Then call the recursive function on the entire list except for the first node.

Update the link on the first node. Return the updated list.

 

Time Complexity = O(n).

Since in the worst case, only one traversal is needed.



Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.

And solve some related problems on the linked list problem

PseudoCode

Algorithm

___________________________________________________________________
procedure recursiveReverse( node* &head):
___________________________________________________________________
1.   if(head==NULL || head->next==NULL)
          return head
2.   node* newHead=recursiveReverse(head->next);
3.   head->next->next=head;
4.   head->next=NULL
5.   Return newHead
end procedure

 

Implementation in C++

#include <iostream>
using namespace std;


//structure of node
class node {
    public:
    int data;
    node* next;
    
    node(int val){
        data=val;
        next=NULL;
    }
};


//fuction to insert a node at the tail
void insertAtTail(node* &head, int val) {
    node* n = new node(val);
    
    if(head==NULL) {
        head=n;
        return;
    }
    
    node* temp = head;
    while(temp->next!=NULL) {
        temp=temp->next;
    }
    temp->next = n;
}


//Display function
void display(node* head) {
    node* temp = head;
    while(temp!=NULL) {
        cout<<temp->data<<"->";
        temp=temp->next;
    }
    cout<<"NULL"<<endl;
}



//function to reverse a node
node* recursiveReverse(node* &head) {
    
    //Base condition
    if(head==NULL || head->next==NULL) {
        return head;
    }
    
    node* newHead=recursiveReverse(head->next);
    head->next->next=head;
    head->next=NULL;
    
    return newHead;
}


int main() {

    node* head = NULL;
    insertAtTail(head, 1);
    insertAtTail(head, 2);
    insertAtTail(head, 3);
    insertAtTail(head, 4);
    insertAtTail(head, 5);
    //displaying original linked list
    display(head);
    node* newhead=recursiveReverse(head);
    //displaying reversed linked list
    display(newhead);

    return 0;
}

 

Output:

Input:  1->2->3->4->5->NULL
Output:  5->4->3->2->1->NULL

Complexity Analysis

Time Complexity: O(n).

In the worst case, all elements are to be traversed once.

∴O(n).

Space complexity: O(n) due to the space consumed by the recursive call stack

Frequently Asked Questions

What is a node?

The collection of the nodes makes a linked list. The node contains the data and the address of the next node.
 

Is it possible to reverse a linked list linearly?

Yes, it is possible to reverse a linked list linear.
 

Is it necessary to initialize the last node address as null?

Yes, as elements are not stored in a contiguous manner, pointers are used, so sometimes it may take the garbage value.

Conclusion

This article taught us how to Recursively reverse a Linked List. We discussed its implementation using illustrations, pseudocode, and then proper code.

We hope you could take away critical techniques like analyzing problems by walking over the execution of the examples and finding out the recursive pattern followed in most linked list problems.

Now, we recommend you practice problem sets based on the linked list to master your fundamentals. You can get a wide range of questions similar to this on CodeStudio

It's not the end. Must solve the problem of similar types. 

Happy Coding!!

Was this article helpful ?
0 upvotes