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
Example 1 Case 1
- Input
list=[1,2,3]- Output
3 2 1
Print after the child returns.
Example 2 Case 2
- Input
list=[7]- Output
7
One node prints once.
Example 3 Case 3
- Input
list=[]- Output
(no output)
Defensive null-head extension.
Hints Optional
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
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.
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:
printReverse(A)
└─ printReverse(B)
└─ printReverse(C)
└─ printReverse(null) returns
C.printValue(); return
B.printValue(); return
A.printValue(); returnAt 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

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.
Recognition and related practice
“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 RangeCompare a different recursive promise and how its parent resumes.