Find a lesson, question or project

Start typing to search published content and planned structures.

↑ ↓ moveEnter openEsc close

Print an Immutable Linked List in Reverse: Java Call-Stack Reasoning

Print backward without changing links or reading hidden fields, using recursive returns, an explicit-stack alternative and an API-faithful dry run.

MediumRecursion and backtrackingPattern: recursion, reversal

Problem statement

Print a singly linked list in reverse order without changing the list. You may only call getNext() and printValue() on the provided node. You cannot read a value field, assign next, or assume how the node is implemented.

The original takeUforward prompt has 1–1000 nodes, with displayed values from −1000 to 1000. For 1 → 2 → 3 → 4, print 4, 3, 2, 1.

Printing backward is not reversing pointers. After the method, the original forward traversal must remain identical.

Constraints & requirements

CONTRACT
You can walk forward but must print backward.

Examples 3 test cases

  1. Example 1 Case 1

    Input
    list=[1,2,3]
    Output
    3 2 1

    Print after the child returns.

  2. Example 2 Case 2

    Input
    list=[7]
    Output
    7

    One node prints once.

  3. Example 3 Case 3

    Input
    list=[]
    Output
    (no output)

    Defensive null-head extension.

Solve on LeetCode ↗

Hints Optional

Hints become more specific one step at a time.
01Find the smaller problem

You can walk forward but must print backward.

02Define the state

What happens if this node waits until its entire suffix has printed?

03Connect the recurrence

Recurse on getNext(), then call printValue(). Null is the base case; never read or mutate hidden fields.

How to think before coding

List the permitted API before coding: only getNext() and printValue(), not hidden fields or pointer updates. A node must print after its successor chain. That places the recursive call before the print statement and makes null the stopping condition. Recursion and an explicit stack both use O(n) memory; neither is an in-place reversal of the immutable list.

Baseline: an explicit stack of references

Java
static void printWithStack(RecursionProblemExamples.ImmutableListNode head) {
    Deque<RecursionProblemExamples.ImmutableListNode> pending = new ArrayDeque<>(); // Store opaque refs.
    for (var node = head; node != null; node = node.getNext()) pending.push(node); // Visit forward only.
    while (!pending.isEmpty()) pending.pop().printValue(); // Newest reference prints first.
}

This takes O(n) time and O(n) explicit storage and avoids recursive stack-overflow risk. It is a valid alternative for the linked API contract. Recursion uses the runtime stack for the same ordering.

Intuition: delay this node until its suffix finishes

Suppose a call owns node A. If its child prints every node after A in reverse, the only unfinished task is printing A.

First recurse, then print. The call stack stores references to nodes while those calls wait. It does not need access to the nodes’ private values.

Recursive solution

This is the same descend-first, print-on-return approach as your local practice/ReverseImmutableLinkedList.java. Its mutable node constructor/setter is a demonstration fixture only: the judge’s immutable interface lets the solution get the next node and print a value, not change links.

The judge supplies ImmutableListNode. Our downloadable companion defines only that interface so it can be tested locally; do not implement or speculate about a judge node in a submission.

Java
public static void printReverse(ImmutableListNode head) {
    if (head == null) return; // Beyond the final node there is nothing to print.
    printReverse(head.getNext()); // Print the entire suffix before printing this node.
    head.printValue(); // This suspended frame resumes after all later nodes were printed.
}

Why null first? The final node’s getNext() returns null. Null is the base-case call that prints nothing. It lets the final real node resume and print first.

Why put printValue after recursion? Before recursion prints head-first; after recursion prints tail-first.

Recursion tree and actual stack

Use node identities A, B, C rather than inspecting hidden fields:

Worked example · read from top to bottom
printReverse(A)
└─ printReverse(B)
   └─ printReverse(C)
      └─ printReverse(null) returns
      C.printValue(); return
   B.printValue(); return
A.printValue(); return

At maximum depth, the top-first call stack is [null, C, B, A]. Each return removes only its top frame. Then the parent resumes. This is a chain, not a branching decision tree.

The trace uses teaching node names to show identities and printed output; the algorithm itself can only call the immutable node API.

Dry run

Numbered illustrated dry run for Print an Immutable Linked List in Reverse: Java Call-Stack Reasoning; the text transcript explains the states.
Follow the numbered panels in order. Open full-size dry run ↗
Read the text transcript
Event Active frame Printed so far
Call through A, B, C null nothing
Null returns C resumes nothing
Print C, return B resumes 3
Print B, return A resumes 3, 2
Print A, return none 3, 2, 1

The displayed values are example outputs of printValue(), not a value-reading API.

Why this is correct

An empty suffix prints nothing. Assuming the rest of the list prints backward correctly, printing head afterward puts head last. By induction, the entire list prints in reverse while no link changes.

Complexity and memory follow-ups

Recursion: O(n) time and O(n) call-stack space, excluding whatever storage the platform uses to capture printed output. Explicit stack: O(n) time and O(n) auxiliary space. Java does not guarantee tail-call elimination, and this method is not tail-recursive anyway: printing remains after the child returns.

A constant-space alternative repeatedly scans from head to the next node that must be printed. It uses O(n²) time and O(1) auxiliary space. With this forward-only opaque API, do not casually promise both linear time and constant space. Block-based approaches can trade O(√n) memory for extra passes, but need their own proof and implementation.

Mistakes and tests

  • Reading head.val violates the API even if a local test class has that field.
  • Reassigning next solves a mutable-list problem, not this one.
  • Skipping the null guard causes a method call on null.
  • [] → no print as a defensive extension; [7] → 7; [2,2,-1] → −1,2,2.
  • Test identities and next references before and after, not only printed values.
  • A very long chain may overflow the runtime stack: use explicit references when needed.

“Forward-only, read through a narrow API, output backward” suggests saving references or delaying work during recursion. Compare stack reversal: that problem mutates a data stack and needs an insert-at-bottom helper; this one does neither.

Company research note

A public LeetCode discussion is community-tagged Meta and includes a reduced-space follow-up. The available search evidence does not establish a dated firsthand interview account, so it is labeled a community discussion, not an exact verified company badge. Checked 3 October 2026.

Final takeaway

The list still points forward. Only the order in which waiting calls print is reversed.

Download all tested Java solutions. These methods use Java 17+; import java.util.* in a standalone program. Use the Java comments and static dry run together to follow each call, return and update.

Practice next

Next lessonStepping Numbers in Java: Grow a Digit Tree Instead of Scanning a Range

Compare a different recursive promise and how its parent resumes.

Back to Recursion and backtracking →