In-Place Reversal & Dummy Nodes
Intermediate · 18 min read · Problem-Solving Patterns, Linked Lists
Reverse, merge and reorder lists without losing a pointer.
Linked-list bugs have a particular flavour: you change one next pointer and suddenly half the list is gone, or you walk into a cycle you created. Two techniques prevent almost all of that. In-place reversal — always save the next node before you change an arrow.
Reversal: save, flip, advance
Step through it. Each node takes three steps, matching the three lines of code. Save marks the arrow about to be lost (dashed). Flip draws the new arrow pointing back. Advance moves prev and cur on. The ∅ circles are null: prev starts on the left one, and the old tail points to the right one.
Dummy nodes: no special case for the head
Whenever the head might change — deleting it, inserting before it, or building a new list — start with a dummy:
Worked problems
Walk to the node before the segment, then repeatedly move the node after cur to the front of the segment:
Practice ladder
Interview questions
- Why use a dummy node?
- Iterative or recursive reversal?
Further reading
Key takeaways
- Reversal: save next, flip the arrow, advance — and return prev.
- Use a dummy node whenever the head can change; return dummy.next.
- Merging and partitioning: build the answer with a dummy head and a tail pointer.
- Complex reorders combine patterns: middle (fast/slow) + reverse + interleave.
- Draw the boxes and arrows; update one assignment at a time.