1. Recursion

Intuition

Recursion naturally reverses the order of operations. When we recurse to the end of the list first and then print on the way back, we effectively print in reverse. The call stack holds all the nodes, and as each call returns, it prints its node's value.

Algorithm

1. If the current node is null, return (base case).
2. Recursively call the function on head.getNext().
3. After the recursive call returns, print the current node's value.

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

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the size of the linked list.

---

2. Using Stack

Intuition

A stack provides Last-In-First-Out (LIFO) ordering, which is exactly what we need to reverse the print order. We traverse the list once to push all nodes onto the stack, then pop them one by one to print in reverse order.

Algorithm

1. Create an empty stack.
2. Traverse the linked list from head to end, pushing each node onto the stack.
3. Pop nodes from the stack one by one and print each node's value until the stack is empty.

class Solution:
    def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
        stack = []
        while head:
            stack.append(head)
            head = head.getNext()

        while stack:
            node = stack.pop()
            node.printValue()

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

Where $n$ is the size of the linked list.

---

3. Square Root Decomposition

Intuition

To reduce space complexity, we can divide the list into blocks of size approximately sqrt(n). We only store pointers to the start of each block, requiring O(sqrt(n)) space. For each block, we use recursion to print in reverse. Since each block is small, the recursion depth stays at O(sqrt(n)).

Algorithm

1. Traverse the list once to count its size n.
2. Calculate block_size as ceil(sqrt(n)).
3. Traverse the list again, storing a pointer to the start of each block in a stack.
4. Pop each block from the stack and use recursion to print that block in reverse. Limit recursion to the block_size to avoid going into the next block.

class Solution:
    def printLinkedListInReverseRecursively(self, head: 'ImmutableListNode', size: int) -> None:
        if size > 0 and head is not None:
            self.printLinkedListInReverseRecursively(head.getNext(), size - 1)
            head.printValue()

    def getLinkedListSize(self, head: 'ImmutableListNode') -> int:
        size = 0
        while head is not None:
            size += 1
            head = head.getNext()
        return size

    def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
        linked_list_size = self.getLinkedListSize(head)
        block_size = math.ceil(math.sqrt(linked_list_size))

        blocks = []
        curr = head
        for i in range(linked_list_size):
            if i % block_size == 0:
                blocks.append(curr)
            curr = curr.getNext()

        while blocks:
            self.printLinkedListInReverseRecursively(blocks.pop(), block_size)

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(\sqrt n)$

Where $n$ is the size of the linked list.

---

4. Divide and Conquer

Intuition

We can use the slow and fast pointer technique to find the middle of any segment. By recursively printing the second half first, then the first half, we achieve reverse order. The recursion depth is O(log n) because we halve the problem at each level.

Algorithm

1. Define a helper function that takes a start and end pointer (end is exclusive).
2. Base case: if start is null or equals end, return. If start.getNext() equals end, print start and return.
3. Use slow and fast pointers to find the midpoint between start and end.
4. Recursively process the second half (from slow to end).
5. Recursively process the first half (from start to slow).
6. Call the helper with head and null to start.

class Solution:
    def helper(self, start: 'ImmutableListNode', end: 'ImmutableListNode') -> None:
        if start is None or start == end:
            return
        if start.getNext() == end:
            start.printValue()
            return

        slow = start
        fast = start

        while fast != end and fast.getNext() != end:
            slow = slow.getNext()
            fast = fast.getNext().getNext()

        self.helper(slow, end)
        self.helper(start, slow)

    def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
        self.helper(head, None)

Time & Space Complexity

• Time complexity: $O(n \cdot \log n)$
• Space complexity: $O(\log n)$

Where $n$ is the size of the linked list.

---

5. Constant Space

Intuition

Without any extra data structures, we can print in reverse by repeatedly finding the last unprinted node. We maintain an end pointer that marks the boundary. Each iteration traverses from head to find the node just before end, prints it, and moves end backward. This uses constant space but requires O(n) traversals.

Algorithm

1. Initialize end to null (representing the position after the last node).
2. While head is not equal to end:
   • Start from head and traverse until finding the node whose next pointer equals end.
   • Print that node's value.
   • Update end to point to this node.

class Solution:
    def printLinkedListInReverse(self, head: 'ImmutableListNode') -> None:
        end = None

        while head != end:
            curr = head
            while curr.getNext() != end:
                curr = curr.getNext()
            curr.printValue()
            end = curr

Time & Space Complexity

• Time complexity: $O(n^2)$
• Space complexity: $O(1)$

Where $n$ is the size of the linked list.

---

Common Pitfalls

Stack Overflow with Deep Recursion

The simple recursive solution uses $O(n)$ stack space. For very long linked lists, this can cause a stack overflow. Consider the square root decomposition or divide-and-conquer approaches to reduce recursion depth to $O(\sqrt{n})$ or $O(\log n)$ respectively.

Printing in Forward Order Instead of Reverse

A common mistake in the recursive approach is calling printValue() before the recursive call, which prints nodes in forward order. The key insight is that the recursive call must happen first, and printing happens after the call returns, so the deepest nodes print first.

Incorrect Block Size Calculation in Square Root Decomposition

When implementing square root decomposition, using integer division for the block size can lead to issues. Use ceil(sqrt(n)) to ensure all nodes are covered. Also, ensure the recursion within each block stops at the block boundary, not at the end of the list.