Answer to Question #238004 in C++ for Myname

Question

Write a program to print all the elements of the single linked list in reverse order. The
algorithm should have linear time complexity and constant space complexity

Answer 1

#include <iostream>
using namespace std;
struct Node {
    int info;
    struct Node* next;
    Node(int info)
    {
        this->info = info;
        next = NULL;
    }
};
 
struct Linked_List {
    Node* head;
    Linked_List()
    {
        head = NULL;
    }
 
    Node* reverse(Node* head)
    {
        if (head == NULL || head->next == NULL)
            return head;
        Node* other = reverse(head->next);
        head->next->next = head;
        head->next = NULL;
 
        return other;
    }
 
    void display()
    {
        struct Node* temp = head;
        while (temp != NULL) {
            cout << temp->info << " ";
            temp = temp->next;
        }
    }
 
    void add(int info)
    {
        Node* temp = new Node(info);
        temp->next = head;
        head = temp;
    }
};
 
int main()
{
    
    Linked_List N;
    N.add(5);
    N.add(12);
    N.add(10);
    N.add(25);
 
    cout << "Initial linked list\n";
    N.display();
    N.head = N.reverse(N.head);
    cout << "\nReversed Linked list \n";
    N.display();
    return 0;
}