Reverse Linked List
Reverse a singly linked list and return the new head.
- The number of nodes in the list is the range [0, 5000].
- -5000 <= Node.val <= 5000
Intuition
Reverse linked list reverses the direction of every pointer in a singly linked list. It is the foundational linked-list manipulation, appearing inside Reorder List, Palindrome Linked List, and Maximum Twin Sum.
The iterative solution walks the list rewriting each next pointer to face backwards. Three pointers are needed, and the reason for the third is the whole lesson:
- Rewriting current.next destroys the link to the rest of the list, so the next node must be saved before the pointer is changed.
So each iteration is four steps in a fixed order: save current.next, point current.next at previous, move previous to current, move current to the saved node.
Getting that order wrong severs the list. Assigning before saving loses everything ahead, and the loop terminates immediately with a one-node result.
previous starts as null, which is correct — the original head becomes the new tail, and a tail points to null.
The loop ends when current is null, at which point previous holds the new head. Returning current instead of previous returns null, since current has walked off the end.
The recursive version reverses the rest of the list first, then sets head.next.next = head and head.next = null. It is shorter but uses O(n) stack space, and the double-pointer assignment is harder to read.
Empty and single-node lists work without special handling — the loop runs zero or one times and returns correctly.
One pass gives O(n) time and O(1) space.
Reach for the three-pointer flip whenever a problem asks you to change the direction of links rather than the values inside them — reverse a list, reverse a sub-list, reverse in groups of k, or check a palindrome list. The giveaway is a follow-up asking for O(1) extra space: that rules out copying into an array and forces in-place pointer rewiring.
Approach
Before reading on: price up what building a second array costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(n) time and O(1) space.
Understand why three pointers
Rewriting current.next destroys the link to the rest of the list, so the successor must be saved first. That is the entire difficulty.
Save before reassigning
Store current.next in a temporary, then point current.next at previous. Reversing this order severs the list and the loop ends after one node.
Advance both trailing pointers
Move previous to current, then current to the saved successor. The window of three slides forward one node per iteration.
Start previous at null
The original head becomes the new tail, and a tail's next is null — so previous must begin as null rather than as the head.
Return previous, not current
When the loop ends current is null and previous holds the new head. Returning current returns null, a common slip.
Note the recursive alternative
Reverse the rest, then set head.next.next = head and head.next = null. Shorter, but O(n) stack space and harder to read.
Cost of the approach
One pass rewriting pointers gives O(n) time and O(1) space. Empty and single-node lists need no special handling.
Solution & live demo
Common pitfalls
Returning curr instead of prev
while curr:
...
curr = nxt
return curr # always Nonewhile curr:
...
curr = nxt
return prev # the old tailThe loop only ends when curr becomes None, so returning curr always returns an empty list. prev is one step behind, which is exactly where the new head sits.
Flipping the pointer before saving the next node
curr.next = prev nxt = curr.next # already overwritten curr = nxt
nxt = curr.next # save first curr.next = prev curr = nxt
Once curr.next is reassigned, the original link to the rest of the list is gone — reading it back just hands you prev, and you walk backwards into an infinite loop. Save the tail before you cut it.
Initialising prev to head
prev = head curr = head
prev = None curr = head
The original head becomes the new tail, and a tail must point at None. Starting prev at head makes node 1 point to itself, producing a cycle that hangs any later traversal.
Edge cases
curr is null from the start; the loop is skipped and prev (null) is returned.
One iteration flips its next to null and prev becomes that node — the unchanged head.
Saving nxt before rewiring guarantees the unprocessed remainder is always reachable.