Reverse a linked list
mediumSaving `next` before overwriting `curr.next` is not defensive coding - it is mandatory. Swap those two lines and the rest of the list becomes unreachable.
O(n)Space O(1)Saved in this browser - no sign-up, nothing sent anywhere.
How reverse a linked list works
Reversing a list in place means turning every next pointer around, one at a time, without losing your grip on what remains. Three pointers do it: prev trails behind, curr is the node being flipped, and next is a saved copy of curr.next - saved because the very next line destroys it.
During the loop the list is really two lists: a reversed prefix hanging off prev and an untouched suffix hanging off curr. Each iteration moves exactly one node from the front of the suffix to the front of the prefix. When curr runs off the end, prev holds the new head.
The order of the four loop lines is everything. Save next, flip curr.next to prev, advance prev, advance curr. Swap the first two and the flip overwrites your only route to the rest of the list - the tail leaks, unreachable. One pass, no allocation: O(n) time, O(1) space.
Step by step
- Take 12, 37, 5, 84. prev starts at null, curr at 12 - the whole list is still the unreversed suffix.
- Save next = 37, then flip: 12's next becomes null, the old prev. Advance: prev = 12, curr = 37.
- Save next = 5 and point 37 at 12. The reversed prefix now reads 37, 12; the suffix is 5, 84.
- Save next = 84 and flip 5's pointer onto 37. Advance again: prev = 5, curr = 84, one node to go.
- 84 is the last node, so the saved next is null. Flip 84 onto 5 and advance - curr is now null.
- The loop exits. prev holds 84, the new head, and the list reads 84, 5, 37, 12 - four flips, no extra memory.
Complexity
| Worst case time | O(n) |
|---|---|
| Space | O(1) |
Reference implementation
Python
def reverse(head):
prev, curr = None, head
while curr:
nxt = curr.next # save before overwriting
curr.next = prev # flip
prev, curr = curr, nxt # advance
return prev # new headJavaScript
function reverse(head) {
let prev = null, curr = head;
while (curr) {
const next = curr.next; // save before overwriting
curr.next = prev; // flip
prev = curr; // advance
curr = next;
}
return prev; // new head
}Java
static Node reverse(Node head) {
Node prev = null, curr = head;
while (curr != null) {
Node next = curr.next; // save before overwriting
curr.next = prev; // flip
prev = curr; // advance
curr = next;
}
return prev; // new head
}Worth noticing
Three pointers, and the order of the four lines is everything
Saving `next` first is not defensive coding - it is mandatory. The very next line overwrites `curr.next`, and without the saved copy the rest of the list becomes unreachable. Swap those two lines and you leak the tail.
The list is two lists during the loop
The reversed prefix hanging off `prev`, and the untouched suffix hanging off `curr`. Every iteration moves exactly one node from the front of the second to the front of the first. Seeing it that way makes the invariant obvious.
O(n) time, O(1) space
One pass, three pointers, no allocation. The recursive version is the same time but O(n) stack - which will overflow on a long list, so the iterative form is what interviewers want.
Common pitfalls
- Flipping before saving: write curr.next = prev before copying curr.next and the rest of the list becomes unreachable - the classic tail leak.
- Returning head instead of prev: after the loop, head still points at the old first node, which is now the tail.
- Adding special cases for empty and single-node lists that the loop already handles - the extra branches are where new bugs arrive.
- Reaching for recursion on long lists: same O(n) time but O(n) stack frames, and a deep enough list overflows the call stack.
Where it is used
- LeetCode 206 and its follow-ups - reversing in ranges, in k-groups, or checking palindromes.
- Palindrome checking on lists: reverse the second half, compare halves, optionally restore.
- The pointer discipline transfers to every in-place rewiring problem - merges, partitions, reordering.
- Interviews use it as the fastest test of whether you can mutate pointers without losing nodes.
Frequently asked questions
What is the time and space complexity of reversing a linked list?
O(n) time and O(1) space for this iterative version: one pass over n nodes with a constant number of pointer writes at each, using just three pointer variables. The recursive version matches the time but spends O(n) space on the call stack.
Why do you need three pointers to reverse a linked list?
Each flip destroys the only link to the remainder of the list, so next must be saved first. prev is the node the arrow will now point at, and curr is the node being flipped. With fewer than three you lose either the tail or the new head.
Is the recursive solution better than the iterative one?
It reads elegantly but costs O(n) stack frames, and a long enough list overflows the stack. The iterative version does the same work in O(1) space, which is why interviewers usually ask for it - or ask for both and the trade-off between them.
How do I avoid losing nodes while reversing?
Keep the invariant in view: prev heads the reversed part, curr heads the untouched rest, and the saved next is the bridge between iterations. If every iteration saves before it flips and then advances both pointers, no node is ever unreachable.