Reversing a Linked List
You'll learn how to flip a linked list's direction by carefully rewiring its next pointers using a three-pointer technique.
The Challenge
In a singly linked list, each node points forward to the next node. To reverse the list, we must make each node point backward to its previous node instead. The trick is doing this without losing track of where we are or where we're going.
The Three-Pointer Strategy
Imagine you're walking through a chain of people holding hands. You want everyone to turn around and hold the other person's hand instead. You need to:
- Remember who's behind you (
previous) - Know where you currently stand (
current) - Remember who's ahead before you let go (
next)
The algorithm works like this:
- Start with
previous = NULL(nothing comes before the first node) - Set
currentto the head of the list - While
currentisn't NULL:- Save
current->nextintonext(don't lose the rest of the list!) - Reverse the pointer: make
current->nextpoint toprevious - Move
previousforward tocurrent - Move
currentforward tonext
- Save
- When done,
previouspoints to the new head
Why Three Pointers?
Without next, you'd lose the rest of the list when reversing current->next. Without previous, you couldn't point backward. Without current, you wouldn't know which node you're working on!
This iterative approach visits each node exactly once, making it O(n) time with O(1) space—no recursion overhead needed.
Key Takeaway: Reversing a linked list requires three pointers (previous, current, next) to safely flip pointer directions one node at a time without losing connections.