1Understand
The idea
A linked list is changed by rewiring next pointers, not by moving values. Before you overwrite a pointer, save what it pointed to. A dummy node in front of the head removes the special case of changing the first node, and reversing is three pointers: previous, current and next.
Intuition
A linked list changes by rewiring next pointers, not by moving values around. Before you overwrite a pointer, save what it pointed to, otherwise you lose the rest of the list.
A dummy node in front of the head removes the special case of changing the first node. Reversal is the three-pointer walk: previous, current, next.
Draw the pointers for one step; most bugs are a missing save or updating in the wrong order.
What you will be able to do
- Use a dummy head to simplify edge cases
- Save next before rewiring
When to use it
- Input is a ListNode head
- Reverse all or part of a list
- Remove nodes matching a condition
2See it
Walkthrough
Reverse a list
1 → 2 → 3, save next, rewire cur.next to prev, advance.
1 / 4
prev = None, cur = head (1). Save nxt before rewiring.
Live template
Line 1 active
Complexity: time O(n), space O(1)
Reversal and most local rewires are O(n) time, O(1) extra space. Recursion uses O(n) stack. Dummy-head patterns for insert/delete are O(1) pointer changes once you have found the spot (finding is still O(n)).
Read the walkthrough as text
Reverse a list. 1 → 2 → 3 → None.
prev = None,cur = 1.- Save
nxt = cur.next. Setcur.next = prev. Advanceprev, cur = cur, nxt. - After step on
1:None ← 1 2 → 3. - After
2:None ← 1 ← 2 3. After3:None ← 1 ← 2 ← 3. Returnprev.
In code:
prev = Nonecur = headwhile cur:nxt = cur.nextcur.next = prevprev, cur = cur, nxtreturn prev
3Recognise it
Kinds of problems (7)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Reverse a list
Example. Reverse a singly linked list in place.
How. prev, cur, nxt walk: cur.next = prev, then shift all three.
Reverse a sub-range or k-group
Example. Reverse every k nodes.
How. Dummy head; reverse k links per segment, stitch ends between groups.
Delete nodes by value
Example. Remove all nodes with val from a linked list.
How. Dummy + prev pointer: skip nodes where cur.val == val by prev.next = cur.next.
Insert into a sorted list
Example. Insert target into sorted linked list.
How. Walk until prev.next.val > target, then splice new node between prev and prev.next.
Add numbers stored as lists
Example. Two lists store digits MSB or LSB, add them.
How. Reverse if needed, or add with carry walking both lists and building result digits.
Deep copy with a node map (random pointers)
Example. Copy list where each node has next and random.
How. Two passes: map old→new, then wire next and random via the map.
Rotate or split by length
Example. Rotate list right by k places.
How. Find tail and length, k %= n, break list at n−k, reattach tail before head.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Lost reference
Why it happens. Rewiring `.next` before saving the successor cuts the list.
How it fails. cur.next = prev before nxt = cur.next, you lose the rest of the list after cur.
Fix. Always `nxt = cur.next`, then rewire, then advance with saved nxt.
Head edge case
Why it happens. The first node is special for delete/insert problems.
How it fails. Delete head node with val: prev is None, you skip wiring the new head.
Fix. Start with `dummy.next = head` and keep a pointer before the current node.
Dangling tail
Why it happens. Splitting or deleting without nulling the old tail `.next`.
How it fails. Partition leaves last node of “less” chain pointing into “greater”, cycle when traversing.
Fix. After split, set tail.next = None on each chain before joining.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.