Problem Breakdown
We are given an ImmutableListNode representing the head of a singly linked list. We must print all node values in reverse order (Tail to Head). The constraints strictly forbid modifying nodes or accessing internal pointers directly; we only have .getNext() and .printValue(). Since we cannot traverse backwards, we need external storage for state—either an explicit stack or implicit call stack—to remember the path back from the tail.
Intuition
To print in reverse order (Tail -> Head) when traversal is naturally forward (Head -> Tail), we must store information about nodes visited before reaching the end to process them later.
- Forward Traversal: We move
head->.getNext()until null. - Backtracking: Once at the tail, as we return from recursive calls (unwinding the stack) or pop an explicit stack, we print the current node’s value.
- Space Constraint: Since we cannot modify nodes to store indices/pointers and lack a direct
.getValue()API that doesn’t trigger side effects, O(N) space is required for storage (either heap-based list of references or system call frames). Constant space complexity without modification is impossible because the order information must be preserved.
Approach
We utilize Recursion to handle the reverse printing logic naturally via post-order traversal behavior:
- Define a helper function
traverse(node). - Base Case: If
nodeis null, return immediately (reached tail). - Recursive Step: Call
traverse(node.getNext())first. This moves the stack pointer down to the end of the list. - Print Action: After the recursive call returns (meaning we are backtracking up from the tail), print the current node’s value using
.printValue().
This approach effectively uses the system’s call stack as our LIFO buffer, avoiding explicit heap memory allocation for a separate data structure while maintaining O(N) space complexity due to recursion depth. Note: For N=1000 in Python, this fits within standard LeetCode limits which often adjust recursion depth, but an iterative solution with an explicit list is also valid if stack overflow risks are prioritized over code brevity.
Complexity Analysis
- Time Complexity: O(N). We visit each node exactly once to traverse down and print on the way up (or back in iteration). Total operations proportional to N.
- Space Complexity:
- Recursive: O(N) due to recursion stack depth required for a list of length N.
- Iterative Alternative: O(N) using an explicit Python list to store node references before printing them in reverse order.
- Follow-up Answer: Constant space complexity is not possible without modifying the linked list structure (e.g., swapping pointers or storing indices). Since we are restricted from modification and lack direct pointer access, auxiliary storage proportional to N is required to maintain traversal state for reversal.
Solution
def printLinkedListInReverse(head):
"""
Prints values of immutable linked list in reverse using recursion.
Args:
head (ImmutableListNode): The starting node of the list provided by LeetCode environment.
Returns:
None (Prints to stdout)
"""
# Helper function for recursive traversal and printing
def traverse(node):
if not node:
return
# Move forward first (recurse towards tail)
traverse(node.getNext())
# Print current value on the way back up from recursion stack
node.printValue()
traverse(head)
Edge Cases Handled
- Empty List: Although constraints specify length >= 1, the base case
if not nodehandles null input gracefully. - Single Element: Recursion depth of 1 works correctly; prints immediately after return from recursive call (which returns instantly).
- Max Depth (N=1000): Fits within standard LeetCode recursion limits for Python, though iterative approach would be safer in strict local environments with default stack sizes.
- Negative Values:
.printValue()handles integer printing correctly regardless of sign; no overflow issues expected given value range [-1000, 1000].