Code Implementation

# """
# This is the ImmutableListNode's API interface.
# You should not implement it, or speculate about its implementation.
# class ImmutableListNode:
#     def printValue(self): # print the value of this node.
#     def getNext(self): # return the next node.
# """

class Solution:
    def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
        stack = []
        node = head
        while node:
            stack.append(node)
            node = node.getNext()
        while stack:
            node = stack.pop()
            node.printValue()
      

/**
 * // This is the ImmutableListNode's API interface.
 * // You should not implement it, or speculate about its implementation.
 * class ImmutableListNode {
 *   public:
 *     void printValue() const; // print the value of this node.
 *     ImmutableListNode* getNext() const; // return the next node.
 * };
 */

class Solution {
public:
    void printLinkedListInReverse(ImmutableListNode* head) {
        std::vector<ImmutableListNode*> stack;
        ImmutableListNode* node = head;
        while (node) {
            stack.push_back(node);
            node = node->getNext();
        }
        for (int i = stack.size() - 1; i >= 0; --i) {
            stack[i]->printValue();
        }
    }
};
      

/**
 * // This is the ImmutableListNode's API interface.
 * // You should not implement it, or speculate about its implementation.
 * interface ImmutableListNode {
 *     public void printValue(); // print the value of this node.
 *     public ImmutableListNode getNext(); // return the next node.
 * };
 */

class Solution {
    public void printLinkedListInReverse(ImmutableListNode head) {
        List<ImmutableListNode> stack = new ArrayList<>();
        ImmutableListNode node = head;
        while (node != null) {
            stack.add(node);
            node = node.getNext();
        }
        for (int i = stack.size() - 1; i >= 0; --i) {
            stack.get(i).printValue();
        }
    }
}
      

/**
 * // This is the ImmutableListNode's API interface.
 * // You should not implement it, or speculate about its implementation.
 * function ImmutableListNode() {
 *     @param {integer} value;
 *     @return {ImmutableListNode}
 *     this.printValue = function() {
 *         ...
 *     };
 *     this.getNext = function() {
 *         ...
 *     };
 * };
 */

/**
 * @param {ImmutableListNode} head
 * @return {void}
 */
var printLinkedListInReverse = function(head) {
    const stack = [];
    let node = head;
    while (node) {
        stack.push(node);
        node = node.getNext();
    }
    while (stack.length) {
        const n = stack.pop();
        n.printValue();
    }
};
      

Problem Description

You are given the head of a singly linked list, where each node is an ImmutableListNode. This special node type only allows you to:

• Print its value using printValue()
• Access the next node using getNext()

Key constraints:

• You cannot modify or reverse the list.
• You cannot create new nodes or change node values.
• There is only one valid solution per input (the reverse print order).

Thought Process

At first glance, printing a linked list in reverse might seem straightforward: just traverse to the end and print as you return. However, the ImmutableListNode restricts us in two major ways:

• We cannot modify the list (no reversing in-place).
• We cannot access values directly, only via printValue().

To optimize, we need a way to remember the nodes as we traverse, so we can print them in reverse order later. Since we can't modify the nodes, a stack (LIFO structure) is a natural fit: we push each node as we traverse, then pop and print in reverse order.

Solution Approach

Here’s how we solve the problem step-by-step:

1. Traverse the List: Start at the head node and follow getNext() to traverse the entire list.
2. Store Nodes: As you visit each node, push it onto a stack (array or vector). This records the order of nodes from head to tail.
3. Print in Reverse: Once traversal is complete, pop nodes from the stack one by one. For each node, call printValue(). Since the stack is LIFO, this prints values from tail to head.

Why a stack? Because it reverses the order of elements: the last node we see becomes the first we print.

Alternative approach: If recursion is allowed and the list is not too long (to avoid stack overflow), we could use recursion to traverse to the end, then print as the call stack unwinds. However, the stack-based approach is more robust and explicit.

Example Walkthrough

Suppose the linked list is: 1 -> 2 -> 3 -> 4

1. We start at node 1, push it to the stack.
2. Move to 2, push to stack.
3. Move to 3, push to stack.
4. Move to 4, push to stack.
5. Now, the stack (from bottom to top) is: [1, 2, 3, 4]
6. Pop 4, print value (prints 4).
7. Pop 3, print value (prints 3).
8. Pop 2, print value (prints 2).
9. Pop 1, print value (prints 1).

The output is: 4 3 2 1 (each printed on a separate line by printValue()).

Time and Space Complexity

Brute-force approach: For each node, traverse to the end and print the last unprinted node. For n nodes, this is O(n^2) time and O(1) space, but highly inefficient.

Optimized stack approach:

• Time Complexity: O(n) — We traverse the list once to push all nodes, and once more to pop and print.
• Space Complexity: O(n) — We store all n nodes in the stack.

If recursion is used, the call stack also uses O(n) space.

Summary

This problem demonstrates how to work with immutable data structures and limited interfaces. The key insight is to use a stack to reverse the order of traversal, enabling us to print the linked list from tail to head without modifying the list or accessing node values directly. The stack approach is efficient, simple, and leverages the LIFO property to elegantly solve the problem within the given constraints.