Print Immutable Linked List in Reverse

You can solve this problem by applying a recursive function to print the values in reverse. By recursively calling the function on the next node before printing the current node’s value, you will print the values in reverse order.

Here’s the code:

1
2
3
4
5
6

class Solution:
    def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
        if head is None:
            return
        self.printLinkedListInReverse(head.getNext())
        head.printValue()

This code first checks whether the current node is None (end of the list). If it is, it returns without doing anything. If it’s not, it first recursively calls itself on the next node, and then prints the value of the current node.

This approach uses constant space complexity (not considering the function call stack), and linear time complexity. If you want to avoid using the call stack, you could use an iterative approach with a stack, but that would require linear space complexity.