LeetCode 1265 - Print Immutable Linked List in Reverse

LeetCode Problem 1265

Difficulty: 🟡 Medium
Topics: Linked List, Two Pointers, Stack, Recursion

Solution

Problem Understanding

This problem gives us a special type of linked list called an immutable linked list. Unlike a normal linked list problem, we are not allowed to access node fields directly. Instead, we can only interact with the list through two provided APIs:

• printValue(), which prints the current node's value
• getNext(), which returns the next node

The task is to print all node values in reverse order.

For example, if the linked list is:

1 -> 2 -> 3 -> 4

the required output is:

4 3 2 1

The important restriction is that the linked list is immutable. We cannot:

• Modify pointers
• Reverse the list
• Store values back into nodes
• Access internal node structure directly

We can only traverse forward using getNext().

The constraints are relatively small, with at most 1000 nodes. This means even recursive solutions are safe in most languages because recursion depth will remain manageable. However, the follow up asks for more advanced complexity optimizations, including:

• Constant extra space
• Linear runtime with sublinear extra memory

These follow ups suggest that the interviewer expects awareness of multiple techniques, not just the simplest stack solution.

Several edge cases are important:

• A single node list
• Negative values
• Duplicate values
• Long lists near the recursion limit
• Ensuring we never attempt to access fields directly

The problem guarantees that the list length is at least 1, so the head is always valid.

Approaches

Brute Force Approach

The most direct approach is to traverse the linked list from beginning to end and store every node into an auxiliary data structure such as an array or stack.

Since we can only move forward through the immutable list, we cannot naturally print in reverse order during traversal. By storing nodes first, we can later iterate backward through the stored collection and call printValue() on each node.

This approach is straightforward:

1. Traverse the list once
2. Push every node into a stack
3. Pop nodes one by one and print them

This works because stacks naturally reverse order due to their Last In First Out behavior.

The main drawback is the extra memory usage. We store all n nodes, so the space complexity becomes linear.

Optimal Approach

A more elegant solution uses recursion.

When traversing recursively, each recursive call moves deeper into the list until the end is reached. Then, as the recursive calls return, nodes are processed in reverse order automatically.

For example:

dfs(1)
  dfs(2)
    dfs(3)
      dfs(4)

Once node 4 reaches the base case, the recursion unwinds:

print 4
print 3
print 2
print 1

This naturally produces reverse order without explicitly storing nodes in a stack.

The recursive call stack itself acts like a stack data structure.

Although recursion still uses O(n) space because of the call stack, the implementation is concise and clean. Given the small constraint of at most 1000 nodes, this solution is practical and commonly accepted as the standard solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force Stack	O(n)	O(n)	Store all nodes in a stack, then print backward
Recursive DFS	O(n)	O(n)	Uses recursion stack to naturally reverse traversal order

Algorithm Walkthrough

Recursive Reverse Printing Algorithm

1. Start from the head node and define a recursive helper function.

The helper function takes the current node as input. Its purpose is to process all later nodes first before printing the current node. 2. Check whether the current node exists.

If the node is None, return immediately. This becomes the recursion base case. 3. Recursively visit the next node first.

Call the helper function on node.getNext() before printing the current node.

This is the key idea. By delaying printing until after deeper recursive calls finish, nodes are printed in reverse order. 4. Print the current node value during recursion unwinding.

Once all later nodes have already been processed, call node.printValue(). 5. Continue unwinding recursively.

Each returning recursive frame prints its node after all subsequent nodes have already been printed.

Why it works

The recursion guarantees that deeper nodes are fully processed before earlier nodes. Since every node waits for its successor to finish before printing, the output order becomes exactly reversed.

Conceptually, recursion creates an implicit stack:

1 -> 2 -> 3 -> 4

becomes:

push 1
push 2
push 3
push 4

Then the recursion unwinds:

pop 4
pop 3
pop 2
pop 1

which produces reverse order correctly.

Python Solution

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

class Solution:
    def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
        
        def dfs(node: 'ImmutableListNode') -> None:
            if not node:
                return
            
            dfs(node.getNext())
            node.printValue()
        
        dfs(head)

The implementation follows the recursive strategy directly.

The inner helper function dfs performs a depth first traversal of the linked list. Instead of printing immediately, it first recursively visits the next node.

Only after all later nodes are processed does the current node print its value. This reversal of processing order is what produces the required reverse output.

The base case handles the end of the list safely. When getNext() eventually returns None, recursion stops.

The outer function simply starts recursion from the head node.

Go Solution

/*   Below is the interface for ImmutableListNode, which is already defined for you.
 *
 *   type ImmutableListNode struct {
 *
 *   }
 *
 *   func (this *ImmutableListNode) getNext() ImmutableListNode {
 *      // return the next node.
 *   }
 *
 *   func (this *ImmutableListNode) printValue() {
 *      // print the value of this node.
 *   }
 */

func printLinkedListInReverse(head ImmutableListNode) {

    var dfs func(ImmutableListNode)

    dfs = func(node ImmutableListNode) {
        next := node.getNext()

        if next != nil {
            dfs(next)
        }

        node.printValue()
    }

    dfs(head)
}

The Go implementation follows the same recursive structure as the Python solution.

One important difference is how nil handling works. In the provided Go interface, the current node itself is guaranteed valid, so we recursively check whether getNext() returns nil before making another recursive call.

Go also uses function variables for recursive closures, which is why dfs is declared before assignment.

Worked Examples

Example 1

Input:

[1,2,3,4]

Linked list:

1 -> 2 -> 3 -> 4

Recursive Traversal Phase

Recursive Call	Current Node
dfs(1)	1
dfs(2)	2
dfs(3)	3
dfs(4)	4
dfs(None)	Base case

Recursion Unwinding Phase

Returning From	Printed Value
dfs(4)	4
dfs(3)	3
dfs(2)	2
dfs(1)	1

Final output:

4 3 2 1

Example 2

Input:

[0,-4,-1,3,-5]

Linked list:

0 -> -4 -> -1 -> 3 -> -5

Traversal Order

Step	Current Node
1	0
2	-4
3	-1
4	3
5	-5

Printing During Unwinding

Step	Printed
1	-5
2	3
3	-1
4	-4
5	0

Final output:

-5 3 -1 -4 0

Example 3

Input:

[-2,0,6,4,4,-6]

Linked list:

-2 -> 0 -> 6 -> 4 -> 4 -> -6

Recursive Stack Growth

Depth	Node
1	-2
2	0
3	6
4	4
5	4
6	-6

Reverse Printing

Order	Printed
1	-6
2	4
3	4
4	6
5	0
6	-2

Final output:

-6 4 4 6 0 -2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited exactly once
Space	O(n)	Recursive call stack stores up to n frames

The runtime is linear because every node participates in exactly one recursive call and one print operation.

The auxiliary space complexity comes from recursion depth. In the worst case, the recursion stack contains all nodes simultaneously before unwinding begins.

Test Cases

# Mock implementation for local testing

class ImmutableListNode:
    def __init__(self, val):
        self.val = val
        self.next = None

    def printValue(self):
        output.append(self.val)

    def getNext(self):
        return self.next

class Solution:
    def printLinkedListInReverse(self, head):
        
        def dfs(node):
            if not node:
                return
            
            dfs(node.getNext())
            node.printValue()
        
        dfs(head)

def build_linked_list(values):
    nodes = [ImmutableListNode(v) for v in values]

    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]

    return nodes[0]

# Test 1: Example case
output = []
head = build_linked_list([1, 2, 3, 4])
Solution().printLinkedListInReverse(head)
assert output == [4, 3, 2, 1]  # standard reverse order

# Test 2: Negative values
output = []
head = build_linked_list([0, -4, -1, 3, -5])
Solution().printLinkedListInReverse(head)
assert output == [-5, 3, -1, -4, 0]  # handles negatives correctly

# Test 3: Duplicate values
output = []
head = build_linked_list([-2, 0, 6, 4, 4, -6])
Solution().printLinkedListInReverse(head)
assert output == [-6, 4, 4, 6, 0, -2]  # duplicates preserved

# Test 4: Single node
output = []
head = build_linked_list([42])
Solution().printLinkedListInReverse(head)
assert output == [42]  # minimal valid input

# Test 5: Two nodes
output = []
head = build_linked_list([1, 2])
Solution().printLinkedListInReverse(head)
assert output == [2, 1]  # simple reversal

# Test 6: All identical values
output = []
head = build_linked_list([7, 7, 7, 7])
Solution().printLinkedListInReverse(head)
assert output == [7, 7, 7, 7]  # repeated values

# Test 7: Large input
output = []
values = list(range(1000))
head = build_linked_list(values)
Solution().printLinkedListInReverse(head)
assert output == values[::-1]  # stress test near constraint limit

Test	Why
[1,2,3,4]	Verifies standard reverse printing
[0,-4,-1,3,-5]	Ensures negative numbers work correctly
[-2,0,6,4,4,-6]	Confirms duplicates are preserved
[42]	Tests smallest valid linked list
[1,2]	Verifies simple two element reversal
[7,7,7,7]	Ensures repeated values are handled correctly
range(1000)	Stress test near maximum input size

Edge Cases

Single Node List

A linked list containing only one node is the smallest valid input. A buggy implementation might incorrectly recurse past the node or fail to print anything. In this solution, recursion reaches the base case immediately after the single node, then correctly prints that node during unwinding.

Duplicate Values

Some implementations accidentally rely on value uniqueness when debugging or storing nodes. This problem does not guarantee unique values. The recursive solution processes nodes themselves rather than values, so duplicates are printed correctly and independently.

Maximum Length List

The list may contain up to 1000 nodes. Recursive solutions with very deep recursion can sometimes cause stack overflow issues. However, the constraint is small enough that standard recursion depth remains safe in practice for this problem. The implementation processes each node exactly once and handles long chains efficiently.

Negative Numbers

The node values may be negative. Since the algorithm never performs arithmetic operations on node values and only prints them directly, negative values require no special handling and are naturally supported.