Master the dummy head, two-pointer, and partition tricks that turn linked list problems from tricky edge-case nightmares into clean, predictable code.
Linked list problems revolve around pointer manipulation. Unlike arrays, you cannot index into position i in O(1). Instead, you traverse nodes one at a time, rewiring .next pointers to merge, split, reverse, or rearrange. The two most powerful techniques are the dummy head (a sentinel node that eliminates head-of-list edge cases) and partitioning with two tails (splitting nodes into separate chains and reconnecting them).
A dummy head node sits before the real head. You build the result list by appending to a tail pointer. When you are done, dummy.next is the real head. No special-casing the first node.
tail.next = chosen; tail = tail.next;
Why a dummy head? Without it, you must write separate logic for "is the result list empty?" versus "append to existing list." The dummy node guarantees the list always has at least one node, so tail.next = ... is always valid. This eliminates an entire class of null-pointer bugs.
Look for these recognition signals in the problem statement. If you spot one, a dummy head or partition approach is very likely the cleanest solution.
"Merge two sorted lists"
"Partition list around x"
"Remove nodes" or "delete given value"
prev and curr."Insert into sorted list" or "reorder nodes"
The key clue: Whenever the problem says "return the head of the modified list" and the head itself might change (due to merging, deletion, or reordering), reach for a dummy head. It costs O(1) extra space and eliminates edge cases completely.
Create a dummy node and a tail pointer. Compare the heads of both input lists. Whichever is smaller gets appended to tail, then advance that list's pointer. Repeat until one list is exhausted, then attach the remainder.
Result: 1 → 2 → 3 → 4 → 5 → 6
dummy.next.Create two dummy heads — one for nodes less than x, one for nodes ≥ x. Walk the original list, appending each node to the appropriate chain. Then connect the two chains and set the last node's next to null.
Nodes < 3 come first, then nodes ≥ 3, preserving original order within each group. Result: 1 → 2 → 2 → 4 → 3 → 5
Two dummies, one stitch: The partition technique generalizes to any "split then reconnect" problem. Both chains get their own dummy head, so you never need to check if a chain is empty before appending. At the end, connect lessTail.next = greaterDummy.next and greaterTail.next = null (to avoid cycles).
Here are the two annotated Java templates. The merge template uses one dummy; the partition template uses two.
// Merge two sorted linked lists using a dummy head ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); // sentinel ListNode tail = dummy; // build result here while (l1 != null && l2 != null) { if (l1.val <= l2.val) { tail.next = l1; // pick from l1 l1 = l1.next; } else { tail.next = l2; // pick from l2 l2 = l2.next; } tail = tail.next; // advance tail } tail.next = (l1 != null) ? l1 : l2; // attach remainder return dummy.next; // skip sentinel }
// Partition list around value x ListNode partition(ListNode head, int x) { ListNode lessD = new ListNode(0); // dummy for < x ListNode greaterD = new ListNode(0); // dummy for ≥ x ListNode less = lessD, greater = greaterD; while (head != null) { if (head.val < x) { less.next = head; // append to less chain less = less.next; } else { greater.next = head; // append to greater chain greater = greater.next; } head = head.next; } greater.next = null; // terminate greater chain less.next = greaterD.next; // stitch chains return lessD.next; }
Always terminate with null. When partitioning, the last node in the "greater" chain might still point to a node in the "less" chain from the original list. Setting greater.next = null before stitching prevents cycles and infinite loops.
Let us trace through merging two sorted lists step by step, showing pointer positions and the growing result at every stage.
Building the merged list using a dummy head and tail pointer.
| STEP | ACTION | A PTR | B PTR | RESULT |
|---|---|---|---|---|
| 1 vs 2 | Pick 1 from A | [4, 7] | [2, 3, 8] | D → 1 |
| 4 vs 2 | Pick 2 from B | [4, 7] | [3, 8] | D → 1 → 2 |
| 4 vs 3 | Pick 3 from B | [4, 7] | [8] | D → 1 → 2 → 3 |
| 4 vs 8 | Pick 4 from A | [7] | [8] | D → 1 → 2 → 3 → 4 |
| 7 vs 8 | Pick 7 from A | [] | [8] | D → 1..4 → 7 |
| Attach | A empty, attach B remainder | [] | [] | D → 1..7 → 8 |
Notice the pattern: Each comparison moves one pointer forward and appends one node. With n + m total nodes, we do exactly n + m comparisons and pointer moves, giving O(n + m) time. The dummy head means zero special cases — the very first append and every subsequent append use the same code path.
These are classic LeetCode problems that use linked list techniques, listed in rough order of difficulty.
Practice tip: Start with #21 (direct application of the merge template) and #86 (direct application of the partition template). Once comfortable, tackle #23 which extends merge to k lists using a min-heap or divide-and-conquer. #138 requires a creative interleaving trick or a hash map to handle random pointers during a deep copy.
Enter two sorted linked lists and step through the merge algorithm. Watch the dummy head, pointer movement, and the merged result building up node by node.
The merge and partition algorithms visit each node exactly once. With n nodes in one list and m in the other, the total work is O(n + m). Each comparison yields one append, so there is no wasted work.
Space: We only create the dummy node(s) — a constant number of extra pointers. The nodes themselves are rewired in place, not copied. Total extra space: O(1).
Exception: Merge k Sorted Lists using a min-heap is O(N log k) time and O(k) space, where N is the total number of nodes and k is the number of lists. The heap holds at most k nodes at any time.
In-place rewiring: Unlike array-based merging which requires O(n + m) extra space for the output array, linked list merging rewires existing nodes. The dummy head is the only allocation. This is one of the rare cases where linked lists are genuinely more space-efficient than arrays.
Dummy head eliminates edge cases. A sentinel node before the real head means you never need to check "is the list empty?" before appending. The first append and every subsequent append use the identical code path: tail.next = node; tail = tail.next.
Two dummies for partition problems. When you need to split a list into two groups (less/greater, odd/even, etc.), give each group its own dummy head. Append nodes to the appropriate chain, then stitch the chains together at the end.
Always terminate with null. After rearranging nodes, the last node in your result might still have a stale .next pointer from the original list. Set it to null to prevent cycles and infinite loops.
Return dummy.next, not dummy. The dummy is a sentinel that should not be part of the result. Always return dummy.next to skip it. This is a common interview mistake — returning the dummy gives a list with an extra leading zero.
Merge k lists with divide-and-conquer or a min-heap. The two-list merge is the building block. To merge k sorted lists, either pair them up and merge bottom-up (like merge sort, O(N log k) time) or use a min-heap to always extract the global minimum across all k list heads.