Print Immutable Linked List in Reverse

How it works

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.

Steps

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.

Complexity

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

Where n is the size of the linked list.

Things to watch for

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.

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

class Solution {
public:
    void printLinkedListInReverse(ImmutableListNode* head) {
        ImmutableListNode* curr;
        ImmutableListNode* end = NULL;

        while (head != end) {
            curr = head;
            while (curr->getNext() != end) {
                curr = curr->getNext();
            }
            curr->printValue();
            end = curr;
        }
    }
};