Reverse a singly linked list, iteratively and recursively.
Iteratively: walk the list with three pointers — prev, current, and next — rewiring each node's pointer as you go. Recursively: reverse the rest of the list, then attach the current head to the new tail. Both are O(n) time, O(1) and O(n) space respectively.
How to think about it
Recognise the pattern
Linked list manipulation — especially reversal — relies on careful pointer rewiring. You cannot index into a linked list, so you carry state in local variables (prev, current) as you walk. The iterative three-pointer pattern appears in dozens of linked-list problems.
Build the approach step by step
Iterative approach:
At each step you want to flip the arrow: instead of current -> next, make current -> prev. But you must save next before overwriting the pointer.
Before: None <- 1 2 -> 3 -> None
^
prev curr
Step: save next=2, set 1->None (was 1->2), advance prev=1, curr=2
After one step: None <- 1 <- 2 3 -> NoneThree variables, no extra data structure — pure O(1) space.
Recursive approach:
Reverse the tail, then hang the current head onto the new tail:
reverse(1->2->3) = reverse(2->3), then 2.next = 1, 1.next = NoneElegant but uses O(n) call stack space.
Complexity
| Approach | Time | Space |
|---|---|---|
| Iterative | O(n) | O(1) |
| Recursive | O(n) | O(n) call stack |
Prefer the iterative version in production — no risk of stack overflow on long lists.