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:
[1, 1000].[-1000, 1000].
Follow up:
Could you solve this problem in:
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.
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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursion | O(n) | O(n) | Best interview solution when the list is immutable and recursion depth is acceptable |
| Explicit Stack | O(n) | O(n) | When recursion depth might cause stack overflow or iterative control is preferred |
[Let's Code!] Print Immutable Linked List in Reverse • csgrinding • 2,027 views views
Watch 7 more video solutions →Practice Print Immutable Linked List in Reverse with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor