Answer to Question #234241 in C for SOM

Question

Reverse a singly linked list using recursion.

Answer 1

#include <iostream>


using namespace std;


struct Node {
    int d;
    struct Node* nt;
    Node(int d)
    {
        this->d = d;
        nt = NULL;
    }
};
  
struct LinkedList {
    Node* h;
    LinkedList()
    {
        h = NULL;
    }
  
    Node* reverse(Node* node)
    {
        if (node == NULL)
            return NULL;
        if (node->nt == NULL) {
            h = node;
            return node;
        }
        Node* node1 = reverse(node->nt);
        node1->nt = node;
        node->nt = NULL;
        return node;
    }
  
    void display()
    {
        struct Node* temp = h;
        while (temp != NULL) {
            cout << temp->d << " ";
            temp = temp->nt;
        }
    }
  
    void push(int d)
    {
        Node* temp = new Node(d);
        temp->nt = h;
        h = temp;
    }
};


int main()
{
    LinkedList a;
    a.push(10);
    a.push(20);
    a.push(30);
    a.push(40);
  
    cout << "Original linked list\n";
    a.display();
  
    a.reverse(a.h);
  
    cout << "\nReversed Linked list \n";
    a.display();
    return 0;
}