Skip to main content
Talentd

Print Immutable Linked List in Reverse - Solution & Explanation

MediumPremiumFree on FleetCodeLinked ListTwo PointersStackRecursion7 min read
Practice this problem

Problem Statement

You are given an immutable linked list, print out all values of each node in reverse with the help of the following interface:

  • ImmutableListNode: An interface of immutable linked list, you are given the head of the list.

You need to use the following functions to access the linked list (you can't access the ImmutableListNode directly):

  • ImmutableListNode.printValue(): Print value of the current node.
  • ImmutableListNode.getNext(): Return the next node.

The input is only given to initialize the linked list internally. You must solve this problem without modifying the linked list. In other words, you must operate the linked list using only the mentioned APIs.

 

Example 1:

Input: head = [1,2,3,4]
Output: [4,3,2,1]

Example 2:

Input: head = [0,-4,-1,3,-5]
Output: [-5,3,-1,-4,0]

Example 3:

Input: head = [-2,0,6,4,4,-6]
Output: [-6,4,4,6,0,-2]

 

Constraints:

  • The length of the linked list is between [1, 1000].
  • The value of each node in the linked list is between [-1000, 1000].

 

Follow up:

Could you solve this problem in:

  • Constant space complexity?
  • Linear time complexity and less than linear space complexity?

Approach Overview

Problem Overview: You receive the head of an immutable linked list where nodes cannot be modified and you cannot access the previous node. The goal is to print the values in reverse order using only the provided printValue() method.

Approach 1: Recursion (O(n) time, O(n) space)

The simplest strategy relies on recursion. Traverse to the end of the linked list first, then print values during the recursion unwind phase. Each recursive call moves one node forward using getNext(). When the recursion reaches the tail, the stack begins returning and each node prints its value in reverse order. This works because the call stack naturally stores nodes in forward order but releases them backward. Time complexity is O(n) since each node is visited once. Space complexity is O(n) due to the recursion stack.

This approach fits perfectly because the list is immutable. You cannot reverse pointers or store references inside nodes, but recursion provides a temporary stack frame for each node.

Approach 2: Explicit Stack (O(n) time, O(n) space)

An iterative alternative uses a stack. Traverse the list from head to tail and push each node reference onto the stack. After reaching the end, pop nodes one by one and call printValue(). Since stacks are LIFO, values come out in reverse order. The algorithm performs one forward traversal and one stack pop per node, giving O(n) time complexity.

This approach mirrors what recursion does internally but gives you explicit control over memory. The downside is extra code and manual stack management. Space complexity remains O(n) because every node must be stored.

Recommended for interviews: Recursion is the expected solution. The problem is designed around the limitation that the linked list is immutable, preventing pointer reversal or in-place modification. Using recursion shows you recognize that the call stack can simulate reverse traversal. Mentioning the stack-based alternative demonstrates understanding of how recursion works under the hood.

Solution

We can use recursion to implement reverse printing of a linked list. In the function, we check whether the current node is null. If it is not null, we get the next node, then recursively call the function itself, and finally print the value of the current node.

The time complexity is O(n), and the space complexity is O(n). Where n is the length of the linked list.

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
RecursionO(n)O(n)Best interview solution when the list is immutable and recursion depth is acceptable
Explicit StackO(n)O(n)When recursion depth might cause stack overflow or iterative control is preferred

Video Solution

[Let's Code!] Print Immutable Linked List in Reverse • csgrinding • 2,030 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Print Immutable Linked List in Reverse easy or hard?
The problem is rated Medium but the core idea is straightforward once you recognize that recursion can simulate reverse traversal. The challenge comes from the immutable constraint, which prevents modifying the list or reversing pointers.
Print Immutable Linked List in Reverse Python/Java solution
The typical Python or Java implementation uses recursion: call the function on the next node, then print the current node value using the provided printValue() method. The logic is identical across languages including C++, Go, TypeScript, and C#.
How to solve Print Immutable Linked List in Reverse in O(n)?
Traverse the immutable linked list to the end using recursion. Call the function on the next node first, then print the current node's value after the recursive call returns. This causes nodes to print in reverse order while maintaining O(n) time complexity.
What is the best approach for Print Immutable Linked List in Reverse?
Recursion is the most common approach. Traverse to the end of the linked list using recursive calls, then print the node values while the recursion stack unwinds. This naturally produces reverse order. The algorithm runs in O(n) time with O(n) recursion stack space.
Is Print Immutable Linked List in Reverse asked at Google/Amazon/Meta?
Variants of immutable data structure problems and recursion-based traversal questions have appeared in interviews at companies like Google and Meta. The problem tests understanding of linked list constraints, recursion, and stack behavior.
What data structure is used in Print Immutable Linked List in Reverse?
The solution relies on the call stack created by recursion or an explicit stack data structure. Both approaches simulate reverse traversal because linked lists only provide forward access to the next node.
What is the time complexity of Print Immutable Linked List in Reverse?
The time complexity is O(n) because each node in the linked list is visited exactly once. Whether you use recursion or a stack, the algorithm performs a single traversal and one print operation per node.

Ready to solve this problem?

Practice Print Immutable Linked List in Reverse with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Remove Nth Node From End of List