Traversal & reversal
Scenario
You need to process a linked list of network packets backwards, but the list only has forward pointers.
How do you reverse the entire list in-place without using extra memory or getting stuck in an infinite loop?
Why it exists
Problem: Navigating backward in a singly linked list is impossible because edges are unidirectional. Reversing the order of elements naively requires copying all values into a stack or array, which uses O(N) extra space and leaves the original list as abandoned memory.
Naive approach: Traverse the list, push all values onto a stack, then pop them out to create an entirely new list.
Better idea: Modify the existing pointers in-place. By maintaining three tracking pointers (previous, current, and next), you can walk through the list and flip each pointer backward one by one, achieving complete reversal in strictly O(1) extra space.
Mental model
Walk through the sequence, holding the current node, reaching out to save the next node, and then turning the current node around to point behind you.
You need three references: 'prev' (initially null), 'curr' (initially the head), and 'next'. Because altering the outgoing edge of a 'curr' node immediately severs the connection to the remainder of the sequence, you must first cache the successor node in 'next'. Then, rewrite 'curr.next' to point backward to 'prev'. Finally, advance your pointers: 'prev' steps forward to 'curr', and 'curr' steps forward to the cached 'next'. This strictly partitions the list into a fully reversed segment and an unreversed segment.
Repeated decision: Have I saved the next node before I flip the current node's pointer?
Explanation
A singly linked list is defined entirely by its edges (pointers) rather than contiguous memory allocation. This means elements are scattered across memory, connected only by unidirectional references. To reverse this structure in-place, you cannot simply swap values; you must systematically rewire the edges.
The iterative reversal algorithm requires three pointers: prev, curr, and next. We start with prev as null and curr at the head of the list. In each step, we must first cache curr.next into our next pointer. This is the most critical operation: if we change curr.next before saving it, we sever our only link to the rest of the list, permanently losing access to those nodes in memory.
Once the next node is safely cached, we can safely overwrite curr.next to point backward to prev. After the edge is flipped, we shift our working window forward. The prev pointer moves up to where curr is, and curr moves up to the cached next node. This loop continues until curr becomes null, meaning we have processed every node. At termination, the prev pointer holds the memory address of the final node processed, which is the new head of our fully reversed list.
Key points
- O(N) Time, O(1) Space: Iterative reversal modifies the structure in a single linear pass using only three pointer variables, maintaining strictly constant extra space.
- Iterative vs. Recursive: While recursive reversal is possible, it requires O(N) space for the call stack and risks a stack overflow fault on long lists. Iterative traversal is the preferred, safe pattern.
- The Null Terminator: The original head node's next pointer must become null to signify the end of the new list, which happens naturally if the previous pointer starts as null.
Pattern: In-place pointer manipulation
Recognition cues:
- Requires reordering a linked list.
- Strict memory constraint (O(1) extra space).
- Terms like 'in-place', 'constant space', or 'pointer rewiring'.
Failure signals
- You are using a stack or array to store node values.
- You are swapping node values instead of modifying the next pointers.
- You encounter a null pointer exception or infinite loop during traversal.
Engineering examples
Network packet processing
Certain telecommunications protocol decoding requires asynchronous packets to be parsed in reverse order of their arrival.
Rewiring pointers in-place minimizes buffer allocation overhead in memory-constrained routing hardware.
Reversing an execution path
In memory-constrained embedded systems, a hardware execution path or event-log chain must be reversed.
Rewiring the pointers in-place is the only way to reverse the path when allocating a stack is impossible due to memory constraints.
When not to use
- Multi-threaded environments requiring concurrent reads: In-place reversal mutates the shared underlying structure, fundamentally breaking concurrent forward reads by other threads. Immutable data structures are preferred here.
- Lists holding primitive values with no memory constraints: If you just need the values reversed and memory is abundant, copying to an array and reading backwards has better performance due to memory caching.
Common mistakes
- Flipping pointers before caching: If you update curr.next to point backward BEFORE saving curr.next into a temporary variable, you sever the rest of the list. Save next, then flip.
- Returning the wrong head node: A common error is returning curr at the end of the algorithm. Since the loop terminates when curr evaluates to null, returning curr returns an empty list. The prev pointer holds the true new head.
- Failing to nullify the original head's next pointer: If the original head's outgoing edge isn't pointed to null (which happens naturally if prev is initialized to null), it creates a circular dependency causing infinite loops.
Recall questions
- Why is the iterative linked list reversal O(1) space?
- What happens if you mutate the current node's next pointer before caching it?
- Which pointer should you return at the end of the reversal algorithm, and why?
Questions & answers
Reverse a linked list iteratively.
Initialize prev to null and curr to head. Loop while curr is not null: save curr.next to next, set curr.next to prev, advance prev to curr, and advance curr to next. Return prev.
Approach: This is the direct application of the three-pointer state machine pattern.
Explain the tradeoff between iterative and recursive linked list reversal.
Iterative reversal uses O(1) extra space and avoids scaling risks. Recursive reversal uses O(N) space for the call stack and risks a stack overflow fault on very long lists.
Approach: Focus on the architectural risk of unbounded call stack depth versus constant space.
Interesting facts
- In languages without automatic memory cleanup, losing the reference to the rest of a linked list during a botched reversal operation results in a permanent memory leak.
Continue learning
Next: Find the middle
Next: Reverse in k-groups
Next: Floyd's cycle detection
Next: Merge two sorted lists
Related: Find the middle
Related: Reverse in k-groups
Related: Floyd's cycle detection
Related: Merge two sorted lists