Prerequisites
Before attempting this problem, you should be comfortable with:
- Linked Lists - Understanding how to traverse a singly linked list using the
getNext()method - Recursion - The call stack naturally reverses order, printing nodes as the stack unwinds
- Stack Data Structure - An iterative alternative that provides LIFO ordering to reverse the print sequence
- Two Pointers (Slow/Fast) - The divide and conquer approach uses this technique to find the middle of a list segment
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
- If the current node is
null, return (base case). - Recursively call the function on
head.getNext(). - After the recursive call returns, print the current node's value.
Time & Space Complexity
- Time complexity:
- Space complexity:
Where 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
- Create an empty
stack. - Traverse the linked list from
headto end, pushing each node onto thestack. - Pop nodes from the
stackone by one and print each node's value until thestackis empty.
Time & Space Complexity
- Time complexity:
- Space complexity:
Where 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
- Traverse the list once to count its size
n. - Calculate
block_sizeasceil(sqrt(n)). - Traverse the list again, storing a pointer to the start of each block in a
stack. - Pop each block from the
stackand use recursion to print that block in reverse. Limit recursion to theblock_sizeto 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:
- Space complexity:
Where 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
- Define a helper function that takes a
startandendpointer (endis exclusive). - Base case: if
startisnullor equalsend, return. Ifstart.getNext()equalsend, printstartand return. - Use
slowandfastpointers to find the midpoint betweenstartandend. - Recursively process the second half (from
slowtoend). - Recursively process the first half (from
starttoslow). - Call the helper with
headandnullto 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:
- Space complexity:
Where 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
- Initialize
endtonull(representing the position after the last node). - While
headis not equal toend:- Start from
headand traverse until finding the node whosenextpointer equalsend. - Print that node's value.
- Update
endto point to this node.
- Start from
Time & Space Complexity
- Time complexity:
- Space complexity:
Where is the size of the linked list.
Common Pitfalls
Stack Overflow with Deep Recursion
The simple recursive solution uses 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 or 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.