Linked-list questions scare people, but almost all of them come down to one template: flip the next pointers as you walk. Master the three-pointer reversal and most of the family falls out.
The idea
Keep three pointers:
- prev — the already-reversed part (starts as
None). - cur — the node you’re currently flipping.
- next — saved before you flip, so you don’t lose the rest of the list.
Each step: remember next = cur.next, rewire cur.next = prev, then slide both forward (prev = cur; cur = next). When cur is None, prev is the new head. O(n) time, O(1) space.
The template
def reverse_list(head):
prev, cur = None, head
while cur:
nxt = cur.next # 1. save the rest
cur.next = prev # 2. flip the pointer
prev = cur # 3. advance prev
cur = nxt # 4. advance cur
return prev # new head
# 1->2->3->4->5 becomes 5->4->3->2->1Draw the pointers on paper the first few times — the one bug everyone hits is losing the next node by flipping before saving it.
Worked example: reverse a sub-range [m, n]
Reverse only positions m..n and splice it back. A dummy head node makes the splicing clean when the reversal touches the head:
def reverse_between(head, m, n):
dummy = ListNode(0); dummy.next = head
prev = dummy
for _ in range(m - 1): # walk to the node before m
prev = prev.next
cur = prev.next
for _ in range(n - m): # repeatedly move the next node to the front
nxt = cur.next
cur.next = nxt.next
nxt.next = prev.next
prev.next = nxt
return dummy.nextWorked example: palindrome linked list in O(1) space
A neat combo of patterns: find the middle (Lesson 5’s fast/slow), reverse the second half, then compare the two halves:
def is_palindrome(head):
# find middle
slow = fast = head
while fast and fast.next:
slow = slow.next; fast = fast.next.next
# reverse second half
prev = None
while slow:
nxt = slow.next; slow.next = prev; prev = slow; slow = nxt
# compare
left, right = head, prev
while right:
if left.val != right.val: return False
left = left.next; right = right.next
return TrueStep-by-step walkthrough
Trace Reverse Linked List on 1 → 2 → 3 → 4. At each node we save next, point cur.next back at prev, then advance both pointers one step.
| cur | prev (cur.next becomes) | saved next | reversed part | remaining |
|---|---|---|---|---|
| 1 | ∅ | 2 | 1 | 2 → 3 → 4 |
| 2 | 1 | 3 | 2 → 1 | 3 → 4 |
| 3 | 2 | 4 | 3 → 2 → 1 | 4 |
| 4 | 3 | ∅ | 4 → 3 → 2 → 1 | ∅ |
After 4 steps prev is the new head: 4 → 3 → 2 → 1 — reversed in place with three pointers and O(1) extra space.
When to reach for it
Signals: the problem is on a linked list and involves reversing (whole, a sub-range, or in k-groups), reordering, checking a palindrome, or adding numbers represented as lists. The three-pointer flip (often with a dummy head) is the recurring tool.
Pitfalls
- Losing the
nextnode. Always savecur.nextbefore you overwritecur.next. This is the universal linked-list bug. - Not using a dummy head. When the head itself might change, a dummy node before the head removes a pile of special cases.
- Null-pointer edge cases. Empty list, single node, reversing to the very end — dry-run these; linked-list bugs love the boundaries.
Recap
Reverse a linked list in place by walking once and flipping each next pointer with three pointers (prev, cur, next): save, flip, advance — O(n) time, O(1) space. This template is the backbone of reverse-whole, reverse-sub-range, reverse-k-groups, palindrome and reorder problems. Use a dummy head to tame edge cases, and never flip before you’ve saved next.
Practice: 10 solved problems on linked-list reversal → — cover each one, solve it yourself, then check the tested code.
Next: Lesson 12 — Tree BFS, traversing trees level by level.