IntermediateLinked List
Reversing a linked list without losing it
Three pointers: prev, curr, next. Save next first, flip curr.next to prev, then step forward. Save before you flip.
The idea
Reversing means pointing every node back at the one before it. The danger: once you change curr.next you've lost the rest of the list, so save it first.
A dummy node before the head is a related trick: it removes the special case when the head itself changes, in merging or removing nodes.
Worked example
1 → 2 → 3
- prev=None, curr=1: save 2, point 1 → None, prev=1, curr=2
- save 3, point 2 → 1, prev=2, curr=3
- save None, point 3 → 2, prev=3, curr=None → new head is 3: 3 → 2 → 1
In code (Python)
def reverse_list(head):
prev, curr = None, head
while curr:
nxt = curr.next # save the rest
curr.next = prev # flip
prev, curr = curr, nxt
return prevO(n) time, O(1) space.
How to spot it
- Reversing all or part of a list, palindrome lists, reorder list.
Common mistakes
- Flipping before saving next.
- Returning head (now the tail) instead of prev.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →