Reverse a Linked List Recursively

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

You can also try this code with Online C++ Compiler

Run Code

Output:

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

You can also try this code with Online C++ Compiler

Run Code

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

Recommended Topic, Floyds Algorithm

Must Read  C Program to Reverse a Number

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 linearly.

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.

Recommended Problem - Reverse a Stack using Recursion

Recommended Reading:

• Doubly Linked List
• What is Recursion
• Print Reverse of a Linked List without Reversing it
• Reverse Doubly Linked List
• Application of Linked Lists
• Reversing a Linked List
• Reverse a Linked List in groups
• Reverse a Linked List(Java)
• Reverse a Linked List(Python)
• Is it Possible to reverse a Linked List in less than O(N)

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!!