1Understand
The idea
Keep a dummy head and a tail pointer, repeatedly attach the smaller of the two current nodes, and advance in that list. When one list runs out, attach the rest of the other in one step. Merging this way is O(n + m) and needs no extra nodes.
Intuition
Keep a dummy head and a tail pointer. Repeatedly attach the smaller of the two current nodes and advance in that list. When one list runs out, attach the rest of the other in one step.
Merging this way is O(n + m) and allocates no extra nodes, you only rewire. The same skeleton merges k lists when combined with a heap, or rebuilds a list after sort.
Dummy + tail means you never special-case "first node".
What you will be able to do
- Use a dummy node
- Attach the remaining tail
When to use it
- Merge two sorted lists
- Interleave or partition a list
2See it
Walkthrough
Merge two sorted lists
A = 1→3, B = 2→4, always take the smaller head.
1 / 6
Dummy head D simplifies tail wiring. a=head of A(1→3), b=head of B(2→4).
Live template
Line 1 active
Complexity: time O(n + m), space O(1)
Time O(n + m), space O(1) extra. Building a new list of fresh nodes is also fine but uses O(n + m) space. For k lists, heap merge is O(N log k); pairwise merge can be O(N log k) too depending on order.
Read the walkthrough as text
Merge two sorted lists. l1 = 1 → 2 → 4, l2 = 1 → 3 → 4.
- Dummy
D,tail = D. - Compare
1vs1: attach either (say from l1), advance that list. - Continue: attach
1(l2),2,3,4, then the remaining4. - Result
D.nextis1 → 1 → 2 → 3 → 4 → 4.
In code:
dummy = tail = ListNode(0)while l1 and l2:if l1.val <= l2.val:tail.next, l1 = l1, l1.nextelse:tail.next, l2 = l2, l2.nexttail = tail.nexttail.next = l1 or l2return dummy.next
3Recognise it
Kinds of problems (4)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Merge two sorted lists
Example. Return head of merged sorted list.
How. Dummy tail; each step attach smaller head; advance that list.
Partition around a value
Example. All nodes < x before nodes ≥ x.
How. Two dummy chains for less and greater; splice together at the end.
Reorder / interleave a list
Example. L0 → Ln → L1 → Ln−1 → …
How. Find middle, reverse second half, merge alternating nodes from both halves.
Sort a list with merge sort
Example. Sort linked list in O(n log n).
How. Find mid with fast/slow, recurse on halves, merge sorted pieces with dummy tail.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Remainder dropped
Why it happens. Loop exits when one list is empty but the other still has nodes.
How it fails. Merge stops at None, remaining 1→2→3 on list B is never attached.
Fix. After the while loop: `tail.next = a or b` once.
Returns the dummy
Why it happens. Returning the helper node instead of the real head.
How it fails. return dummy, caller gets a node with no value instead of the merged chain.
Fix. return dummy.next, dummy is only a write anchor.
Tail not advanced
Why it happens. Linking without moving tail builds a self-loop or overwrites the same link.
How it fails. tail.next = a repeatedly without tail = tail.next, every node points to the same first node.
Fix. After each attach: `tail = tail.next`.
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.