In-place Reversal
Flip one arrow at a time with prev, curr, next.
- Brute force
- O(n) time, O(n) space — copy to an array and rebuild
- With the pattern
- O(n) — each node rewired once
- Extra space
- O(1)
In plain English
“A conga line where each person holds the shoulder of the person ahead. To turn the line around, you walk along it and ask each person to let go and hold the person who was behind them instead — but before they let go, you note who was ahead so you don't lose the rest of the line.”
Why it's fast
Copying into an array and rebuilding costs O(n) extra memory. Reversal rewires each next pointer in place, using just three references: the node you came from (prev), the node you're on (curr), and a saved handle to the rest (nxt). Each node is touched once — O(n) time, O(1) space.
Spot it when the problem says…
- reverse the linked list
- reverse between positions left and right
- reverse in groups of k
- in-place, O(1) memory
- swap nodes in pairs
- compare first half with reversed second half
Visualize
Reverse a linked list in place
Reverse a singly linked list by re-pointing each node's next — no new nodes.
prev starts at None, curr at the head. Every arrow currently points right.
1def reverse_list(head):2 prev = None3 curr = head4 while curr:5 nxt = curr.next # remember the rest6 curr.next = prev # flip the arrow7 prev = curr # step prev forward8 curr = nxt # step curr forward9 return prevvariables
- prev
- None
- curr
- 1
How to apply it
- 01Set
prev = None,curr = head(use a dummy node if the head can change). - 02Save
nxt = curr.nextbefore touching anything. - 03Point
curr.next = prev. - 04Advance:
prev = curr,curr = nxt. Repeat untilcurris None;previs the new head.
Variations you'll meet
Full reversal
The visualizer's example.
def reverse_list(head): prev, curr = None, head while curr: nxt = curr.next # save the rest curr.next = prev # flip the arrow prev, curr = curr, nxt return prevReverse a sublist (left..right)
Walk a dummy to the node before left, then repeatedly move the next node to the front of the sublist.
def reverse_between(head, left: int, right: int): dummy = ListNode(0, head) before = dummy for _ in range(left - 1): before = before.next curr = before.next for _ in range(right - left): moved = curr.next curr.next = moved.next moved.next = before.next before.next = moved return dummy.nextReverse in k-groups
Check k nodes exist, reverse them, reconnect the previous group's tail to the new head, repeat.
Recursive reversal
new_head = reverse(head.next); head.next.next = head; head.next = None. Elegant, but O(n) stack.
Common mistakes
- Overwriting
curr.nextbefore saving it — the rest of the list is lost. - Returning
curr(None) instead ofprevat the end. - Forgetting a dummy node when the head itself gets reversed, then losing the new head.
- Not reconnecting the reversed segment's tail to the remainder (sublist / k-group).
Practice ladder
Easy → hard. Tick them off as you go.
Think you've got it?
Let the AI interviewer throw a In-place Reversal problem at you and grade how you explain it.