Print Immutable Linked List in Reverse - CPP Solution

1. Introduction

In this blog post, we address a unique challenge: printing an immutable linked list in reverse order. This problem tests our ability to traverse and manipulate data without altering the original list structure.

Problem

The task is to print the elements of a given immutable singly linked list in reverse order.

2. Solution Steps

1. Traverse the list and push each node's value onto a stack.

2. Pop elements from the stack and print them, which will result in a reversed order.

3. This approach allows us to reverse the order of the elements without modifying the linked list.

3. Code Program

#include <iostream>
#include <stack>
using namespace std;

// ListNode structure definition
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// Function to print the linked list in reverse
void printInReverse(ListNode* head) {
    stack<int> s;
    ListNode* current = head;

    // Traverse the list and push the values onto the stack
    while (current != nullptr) {
        s.push(current->val);
        current = current->next;
    }

    // Pop and print each value from the stack
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
}

int main() {
    // Creating an immutable linked list: 1 -> 2 -> 3 -> 4 -> 5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    printInReverse(head); // Expected output: 5 4 3 2 1
    return 0;
}

Output:

5 4 3 2 1

Explanation:

The printInReverse function leverages a stack to reverse the order of elements in the list. 

By traversing the list and pushing each element's value onto the stack, we can then pop and print each element, resulting in a reversed-order printout of the list's elements. 

This method effectively reverses the order for printing without modifying the original list, maintaining its immutability.