Reverse Linked ListReversing a list
The three-pointer iterative form and the recursive one.
Used for: Core pointer practice; very common in interviews
01Why it exists
Reverse Linked List is the warm-up question at almost every company, and above it sit reversing a range, reversing in groups of k, and checking whether a list is a palindrome. All of them are built on the same three-pointer move.
Why this fitsReversing a list is the purest exercise in pointer manipulation: each node does exactly one thing — turn its arrow around — but get the order wrong and the whole list breaks. Practise until you write it without thinking, because every later linked-list problem is a variation on this move.
Two large numbers stored as lists have to be added (with the ones digit at the end), or a list has to be checked for reading the same forwards and backwards. A list can only be walked forwards; there is no way to read it from the tail.
Why this fitsReverse the second half and you can walk inwards from both ends at once. This is the standard trick for handling a backwards problem in O(1) space, and it is cheaper in memory than copying the list into an array.
Same task: the iterative version needs three pointers, the recursive version is four lines but costs an O(n) call stack. Give recursion a long enough list and it blows up.
Why this fitsThere is no better problem for putting the two styles side by side. The iterative version is what you should ship, and the recursive one is the finest example of the "trust a smaller copy of yourself" way of thinking.
Reach for it when you see:Reversing, reading backwards, starting from the tail, palindrome lists, groups of k, reversing a range, the prev / cur / next trio of pointers.
02The core idea
Reversing a list means turning every node's next arrow around: what pointed forwards now points backwards. There is only one hard part — the moment you overwrite cur.next, the way forward is gone. So every step has to save the next node first and change the pointer second.
The iterative version uses three pointers. prev is the head of the part already reversed, starting as None; cur is the node being processed; nxt holds the way forward. Each round does four things: save nxt, turn the arrow, advance prev, advance cur. When the loop ends cur is None and prev is sitting on the original last node, which is the new head. O(n) time and O(1) extra space.
The recursive version thinks about it differently: trust reverse(head.next) to reverse the rest and return its new head. Then there is only one thing left to do — the original next node is now the tail of that reversed part, so point its next back at yourself and set your own next to None. The code is shorter, but the call stack is O(n), so a long enough list overflows it.
Reversing a range is the common variation. Use head insertion: keep cur fixed on the first node of the range and repeatedly lift the node after cur out and splice it in at the front of the range, right − left times. With a dummy node in front, left = 1 needs no special case.
03The algorithm
- 1
prev = Noneandcur = head. - 2Loop while
cur. Inside, first donxt = cur.nextto keep hold of the way forward. - 3
cur.next = prevturns the arrow around. This is the only line that actually changes the structure. - 4
prev = curandcur = nxtstep both pointers forward together. The order matters: the other way round, cur loses track of the original next node. - 5When the loop ends, return
prev. Run it once each on an empty list, a single node and two nodes to check the boundaries.
04Interactive demo
Step through the iterative version and watch how each round's four moves turn one node's arrow around. Green marks the part already reversed, and prev always sits at its head.
Each arrow is that node's next pointer: → points right, ← points left, ∅ points at None. Green means the arrow has already been flipped.
1def reverse(head):2 prev, cur = None, head3 while cur:4 nxt = cur.next5 cur.next = prev6 prev = cur7 cur = nxt8 return prev
05Code
The iterative version, the recursive version, and reversing a range by head insertion. All three are worth writing by hand once, and in the recursive one pay particular attention to what the line head.next.next = head is doing.
# Iterative: three pointers, turning one arrow around per node. O(n) time, O(1) space
def reverse(head):
prev, cur = None, head
while cur:
nxt = cur.next # 1. remember the way forward first
cur.next = prev # 2. turn the arrow around
prev = cur # 3. advance both pointers
cur = nxt
return prev # prev ends up on the original last node
# Recursive: trust reverse(head.next) to reverse the rest and hand back the new head,
# then just point the original next node's next back at yourself. O(n) space (the call stack)
def reverse_rec(head):
if head is None or head.next is None:
return head
new_head = reverse_rec(head.next)
head.next.next = head # that node is the tail now, so hook it back to me
head.next = None # and I become the new tail
return new_head
# Reverse the range [left, right] (LeetCode 92): head insertion
def reverse_between(head, left, right):
dummy = ListNode(0, head)
before = dummy
for _ in range(left - 1):
before = before.next # before stops just ahead of the range
cur = before.next # cur never moves; each round lifts the node after it to the front of the range
for _ in range(right - left):
moved = cur.next
cur.next = moved.next
moved.next = before.next
before.next = moved
return dummy.next06Practice
- LeetCode 206Reverse Linked ListEasy
- LeetCode 234Palindrome Linked List (find the middle, then reverse the second half)Easy
- LeetCode 92Reverse Linked List II (reverse a range)Medium
- LeetCode 24Swap Nodes in PairsMedium
- LeetCode 25Reverse Nodes in k-GroupHard