Problem Description

You are given the head of an immutable linked list, which means you cannot modify the list structure or node values directly. Your task is to print all values of the linked list nodes in reverse order.

The linked list is accessed through a special interface called ImmutableListNode that provides only two methods:

• printValue(): Prints the value of the current node
• getNext(): Returns the next node in the linked list

You cannot access the ImmutableListNode implementation directly or modify the linked list in any way. You must work exclusively with these two provided methods.

For example, if the linked list contains values 1 -> 2 -> 3 -> 4, your solution should print the values in the order: 4, 3, 2, 1.

The key challenge is that you can only traverse the list forward (using getNext()), but you need to print the values in reverse order. The solution uses recursion to achieve this - it traverses to the end of the list first, then prints values as the recursive calls return, effectively printing from tail to head.

The recursive approach works by:

1. Recursively calling the function with the next node until reaching the end of the list (null)
2. As the recursive calls return, printing the value of each node
3. This ensures that nodes deeper in the list (closer to the tail) are printed before nodes closer to the head

Intuition

When we need to print a linked list in reverse order but can only traverse it forward, we face a fundamental problem: we need to know what comes later before we can print it first. This is like reading a book from the last page to the first, but you can only flip pages forward.

The key insight is that we need to somehow "remember" all the nodes we've seen as we traverse forward, then process them in reverse order. Since we cannot modify the list or store nodes directly, we need a way to implicitly store this information.

Recursion naturally provides this mechanism through the call stack. When we make recursive calls, each function call is pushed onto the stack, creating a natural LIFO (Last In, First Out) structure. This is perfect for our needs because:

1. As we traverse forward through the list making recursive calls, we're essentially "storing" each node in the call stack
2. When we reach the end (null node), the recursion starts unwinding
3. As each recursive call returns, we're processing nodes in reverse order - exactly what we want

The beauty of this approach is that the recursive call self.printLinkedListInReverse(head.getNext()) happens before head.printValue(). This means we traverse all the way to the end of the list first, building up our call stack, and only then start printing values as we return from each recursive call. The last node reached (the tail) becomes the first to print its value, the second-to-last node prints next, and so on, until finally the head node prints last.

This leverages the natural behavior of recursion to solve our reversal problem without needing any explicit data structures or list modifications.

Learn more about Stack, Recursion, Linked List and Two Pointers patterns.

Solution Approach

The solution implements a recursive approach to print the linked list in reverse order. Let's walk through the implementation step by step:

Base Case: The function first checks if head is not null with if head:. This serves as our base case - when we reach the end of the list (where head is null), the recursion stops and begins unwinding.

Recursive Step:

self.printLinkedListInReverse(head.getNext())

This line is the core of our recursion. Before doing anything with the current node, we make a recursive call with the next node. This ensures we traverse all the way to the end of the list first.

Processing Step:

head.printValue()

This line executes after the recursive call returns. Due to the nature of recursion, this happens in reverse order - the last node's printValue() is called first, then the second-to-last, and so on.

Execution Flow Example: For a list 1 -> 2 -> 3 -> null, the execution would be:

1. Call with node 1: Recursively calls with node 2
2. Call with node 2: Recursively calls with node 3
3. Call with node 3: Recursively calls with null
4. Call with null: Base case hit, returns immediately
5. Back in call with node 3: Prints 3
6. Back in call with node 2: Prints 2
7. Back in call with node 1: Prints 1

The call stack naturally reverses the order of operations. Each recursive call waits for all subsequent calls to complete before executing its printValue(), achieving the reverse printing without any additional data structures.

Time and Space Complexity:

• Time Complexity: O(n) where n is the number of nodes, as we visit each node exactly once
• Space Complexity: O(n) due to the recursive call stack depth equal to the length of the list

Example Walkthrough

Let's walk through a concrete example with a linked list containing values 5 -> 8 -> 2.

Initial Setup:

• We have an immutable linked list: 5 -> 8 -> 2 -> null
• Our goal is to print: 2, 8, 5

Step-by-Step Execution:

1. First Call - Node 5:

   • printLinkedListInReverse(node_5) is called
   • Check: Is node_5 not null? Yes, continue
   • Make recursive call: printLinkedListInReverse(node_5.getNext()) → calls with node_8
   • (Waiting for recursive call to return before printing 5...)

2. Second Call - Node 8:

   • printLinkedListInReverse(node_8) is called
   • Check: Is node_8 not null? Yes, continue
   • Make recursive call: printLinkedListInReverse(node_8.getNext()) → calls with node_2
   • (Waiting for recursive call to return before printing 8...)

3. Third Call - Node 2:

   • printLinkedListInReverse(node_2) is called
   • Check: Is node_2 not null? Yes, continue
   • Make recursive call: printLinkedListInReverse(node_2.getNext()) → calls with null
   • (Waiting for recursive call to return before printing 2...)

4. Fourth Call - Null:

   • printLinkedListInReverse(null) is called
   • Check: Is null not null? No, base case reached
   • Function returns immediately without doing anything

5. Unwinding - Back to Node 2:

   • The recursive call returns to node_2's context
   • Now executes: node_2.printValue() → Prints: 2
   • Function returns

6. Unwinding - Back to Node 8:

   • The recursive call returns to node_8's context
   • Now executes: node_8.printValue() → Prints: 8
   • Function returns

7. Unwinding - Back to Node 5:

   • The recursive call returns to node_5's context
   • Now executes: node_5.printValue() → Prints: 5
   • Function completes

Final Output: 2, 8, 5 ✓

The key insight is that each node's printValue() is only called after all nodes that come after it have been processed. The recursion builds up a "stack" of pending print operations, then executes them in reverse order as it unwinds.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The recursive function visits each node in the linked list exactly once. Starting from the head, it traverses to the end of the list through recursive calls to head.getNext(), then prints each node's value as the recursion unwinds. Since we perform a constant amount of work (calling getNext() and printValue()) for each of the n nodes, the total time complexity is O(n).

Space Complexity: O(n)

The space complexity is determined by the recursive call stack. Since the function recursively calls itself for each node before printing any values, the maximum depth of the recursion equals the length of the linked list. Each recursive call adds a new frame to the call stack, storing the local variable head and the return address. With n nodes in the list, we have n recursive calls simultaneously on the stack before the first printValue() is executed, resulting in O(n) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Stack Overflow for Large Lists

The recursive solution uses O(n) stack space, which can cause a stack overflow error for very large linked lists (typically lists with thousands of nodes, depending on the system's stack size limit).

Why it happens: Each recursive call adds a new frame to the call stack. For a list with 10,000 nodes, you'll have 10,000 recursive calls stacked up before any printing begins.

Solution - Iterative Approach with Explicit Stack:

class Solution:
    def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
        # Use an explicit stack to store nodes
        stack = []
        current = head
      
        # Traverse the list and push all nodes to stack
        while current:
            stack.append(current)
            current = current.getNext()
      
        # Pop from stack and print (achieves reverse order)
        while stack:
            stack.pop().printValue()

2. Missing Base Case Check

A common mistake is forgetting to check if head is None before making recursive calls, leading to AttributeError when trying to call methods on a None object.

Incorrect Implementation:

def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
    # Missing null check - will crash when head is None
    self.printLinkedListInReverse(head.getNext())  # Error if head is None
    head.printValue()  # Error if head is None

Correct Implementation: Always check if the node exists before accessing its methods:

def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
    if head:  # Essential null check
        self.printLinkedListInReverse(head.getNext())
        head.printValue()

3. Attempting to Modify the List

Since the list is immutable, trying to reverse it in-place or modify node connections will fail. Some might instinctively try approaches like:

Wrong Approach:

# This won't work - can't modify immutable nodes
prev = None
current = head
while current:
    next_node = current.getNext()
    current.next = prev  # Can't do this - no setter available
    prev = current
    current = next_node

The immutable nature forces us to use either recursion or auxiliary data structures to achieve the reverse printing without modifying the original list structure.