Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Use a dummy head and a tail pointer. Walk both lists; each step splice the smaller current node onto tail and advance that list and the tail. When one list empties, attach the entire remainder of the other in one link — it's already sorted. Return dummy.next. O(n + m) time, O(1) space, no new nodes.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you reach for a dummy head to avoid head-initialization edge cases and finish by splicing the leftover list in O(1) rather than node by node.
Where candidates slip
Writing tangled first-node logic without a dummy, or forgetting to attach the remaining list after the loop, dropping its nodes.
How to stand out
Use the dummy node, return dummy.next, splice the remainder in one assignment, and note this is exactly the merge step of merge sort and the building block of merge k sorted lists.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewMerge two sorted listsNeed O(1) space?YesNo / prefer recursionExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2 · Optimal
Iterative — Dummy Node + Tail Splice (Optimal)
1Hint 1Explore hintHide hint
You're building a new chain whose head you don't know until you compare the first two values. What if a fake node sat in front of the real head so the first append looks like every other append?
2Hint 2Explore hintHide hint
Keep a tail pointer starting on the dummy. Each step compare the two current heads, splice the smaller onto tail.next, advance that list, then advance tail.
3Hint 3Explore hintHide hint
When one list runs out, the other is already sorted — set tail.next to whichever list still has nodes, in one assignment, then return dummy.next.
A · Core idea
We assemble the merged list by always appending the smaller of the two current heads, anchored by a dummy sentinel.
Why the dummy node. Building a linked list normally forces an annoying special case: the first node has no predecessor to attach to, so you'd write if (head == null) head = node; else tail.next = node;. A dummy node placed before the real head means tail always has a valid .next to write — including the very first append. One uniform path, zero edge cases. The real list begins at dummy.next.
The merge loop. While both lists have nodes, compare list1.val and list2.val, splice the smaller node onto tail.next, advance that list's pointer, and move tail onto the node just attached. Using <= makes equal values take from list1 first, keeping the merge stable.
Why the leftover splice is O(1). The loop exits the moment one list empties. The other is non-empty and already sorted and entirely ≥ everything appended so far (we always took the smallest available). So we don't iterate it — we point tail.next at its head and the whole tail comes along for free.
Why we splice, not copy. We rewire the next pointers of the original nodes instead of allocating new ones, keeping space at O(1) — the problem expects splicing the existing nodes.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
list1 = [1, 2, 4], list2 = [1, 3]Array state
attach 1 (l1)
1 <= 1 → take l1
[1, 1, 2, 3, 4]C · Code with teaching comments
D · Why it works and complexityO(n + m) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
A dummy head turns 'build a list' into a branch-free loop, and 'attach the rest in one link' exploits the fact that a sorted remainder needs no further work. Together they are the entire merge phase of merge sort on linked lists.
ComplexityO(n + m) time, O(1) space — Each comparison advances one of the two pointers, so at most n + m iterations, each O(1). The leftover splice is one O(1) link. Only a dummy and a tail pointer are used → O(1) space.
E · Edge cases and pitfalls7list1 = [], list2 = [] — Loop body never runs; tail.next = null; return dummy.next = null.Explore edge casesHide edge cases
Edge cases handled
list1 = [], list2 = []Loop body never runs; tail.next = null; return dummy.next = null.list1 = [5], list2 = []Loop skipped (list2 null); tail.next = list1; returns [5].list1 = [2], list2 = [1]First compare takes l2(1), loop ends, tail.next = list1(2) → [1, 2].
Pitfalls
- Returning dummy instead of dummy.next — leaks the sentinel value into the result.
- Forgetting tail.next = leftover, dropping the unfinished list entirely.
- Allocating new nodes per value instead of splicing — wastes O(n + m) memory.
- Forgetting to advance tail — the next splice overwrites the link you just made.
Approach 2 of 2
Recursive — Pick Smaller Head, Recurse on the Rest
1Hint 1Explore hintHide hint
If you knew the merge of the two tails, how would you build the full answer? Attach the smaller head in front of it.
2Hint 2Explore hintHide hint
Base cases: if either list is null, the merged result is simply the other list.
3Hint 3Explore hintHide hint
Otherwise compare the two heads; the smaller one's next becomes the merge of (its rest) with the other list, and you return that smaller head.
A · Core idea
We define the merge in terms of itself: the merged list is the smaller of the two heads followed by the merge of everything else.
Base cases first. If list1 is null, the merge is just list2 (already sorted); symmetrically if list2 is null. These stop the recursion and supply the tail of the final chain.
The recursive step. Compare the two heads. Say list1.val <= list2.val. Then list1 is the smallest unused node, so it comes next: set list1.next = merge(list1.next, list2) — recursively merging the rest of list1 with all of list2 — and return list1. The mirror case handles list2 being smaller.
Why it's correct. At every call the smallest remaining node across both lists is chosen as the local head, and by induction the recursive call correctly merges the strictly smaller remaining problem. The chain of returned heads is therefore globally sorted.
The trade-off. It reads beautifully and needs no dummy node, but each unmerged node adds a stack frame. On long lists (up to 5·10⁴ here) the iterative O(1)-space version avoids any stack-overflow risk — which is why it's the safer lead.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
list1 = [1, 2], list2 = [1, 3]Interactive diagram
How the recursion builds the chain
merge([1,2],[1,3])Each call fixes the smaller head and defers the rest; the base case returns the leftover sorted list.
[1, 1, 2, 3]C · Code with teaching comments
Reference implementation previewpublic ListNode mergeTwoSortedLists(ListNode list1, ListNode list2) { if (list1 == null) return list2; if (list2 == null) return list1; if (list1.val <= list2.val) { list1.next = mergeTwoSortedLists(list1.next, list2);Explore the full codeHide the full code
D · Why it works and complexityO(n + m) timeO(n + m) spaceOpen the invariant and proofExplore the proofHide the proof
Recursion expresses the merge as 'smallest head + merge of the rest', mirroring the iterative splice but offloading the bookkeeping to the call stack. Same O(n + m) time, but you trade O(1) space for O(n + m) frames.
ComplexityO(n + m) time, O(n + m) space — One recursive call consumes one node, so n + m calls total → O(n + m) time. The recursion depth equals the number of nodes → O(n + m) stack space.
E · Edge cases and pitfalls3Forgetting a base case — infinite recursion or a null dereference.Explore edge casesHide edge cases
Pitfalls
- Forgetting a base case — infinite recursion or a null dereference.
- Returning the recursive result instead of the chosen head node.
- Ignoring stack depth on long lists where the iterative version is safer.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; }Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Dropping the remaining list
The loop exits as soon as one list empties; the other still has sorted nodes that must be spliced on. Omit this and you lose data.
Explore the code comparisonHide the code comparison
Dropping the remaining list
The loop exits as soon as one list empties; the other still has sorted nodes that must be spliced on. Omit this and you lose data.
Don't write this
while (list1 != null && list2 != null) {
// ... splice smaller ...
}
return dummy.next; // remaining nodes never attached!Write this instead
while (list1 != null && list2 != null) {
// ... splice smaller ...
}
tail.next = (list1 != null) ? list1 : list2;
return dummy.next;2Returning the dummy sentinel
dummy holds a placeholder value (often 0). The real merged list begins at dummy.next; returning dummy prepends a bogus node.
Explore the code comparisonHide the code comparison
Returning the dummy sentinel
dummy holds a placeholder value (often 0). The real merged list begins at dummy.next; returning dummy prepends a bogus node.
Don't write this
tail.next = list1 if list1 else list2
return dummy # bogus leading nodeWrite this instead
tail.next = list1 if list1 else list2
return dummy.next3Forgetting to advance the tail
After tail.next = chosen, the next iteration writes tail.next again — overwriting the node you just attached unless you move tail forward first.
Explore the code comparisonHide the code comparison
Forgetting to advance the tail
After tail.next = chosen, the next iteration writes tail.next again — overwriting the node you just attached unless you move tail forward first.
Don't write this
if list1.val <= list2.val:
tail.next = list1
list1 = list1.next
# missing: tail = tail.nextWrite this instead
if list1.val <= list2.val:
tail.next = list1
list1 = list1.next
tail = tail.nextRevise
Carry the pattern into the interview
Pattern to remember
Dummy node + tail pointer two-pointer splice
Code pattern to memorize
dummy = ListNode()
tail = dummy
while a and b:
if a.val <= b.val: tail.next = a; a = a.next
else: tail.next = b; b = b.next
tail = tail.next
tail.next = a if a else b
return dummy.nextRules to remember
- 1Use a dummy head so the first splice uses the same code as every other — no
if head == nullbranch. - 2Return
dummy.next, neverdummy— the dummy is a throwaway sentinel. - 3After the loop, attach the remaining list wholesale with one link:
tail.next = a or b. - 4Use
<=(not<) on ties to keep the merge stable; either is sorted,<=is conventional. - 5Splice existing nodes — don't allocate new ones — to stay O(1) space.
Use this pattern when
- Merge two already-sorted singly linked lists into one sorted list
- The merge step of merge sort on a linked list
- Combining sorted streams where random access is unavailable
- Building block for merging k sorted lists
Choose another pattern when
- Inputs are arrays with random access → index-based merge or a library sort may be simpler
- You must merge many lists at once → use a min-heap (merge k sorted lists), not naive pairwise loops
- Lists are unsorted → sort first; this assumes sorted inputs
- You can't mutate the inputs → you'd copy nodes, costing O(n + m) space
Interview takeaway
The dummy-node + tail pattern strips every 'is this the first node?' edge case out of list building, and 'attach the sorted remainder in one link' avoids needless work. It's the backbone of merge k sorted lists, the merge phase of list merge sort, and Add Two Numbers.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternDummy-node + tail-pointer list construction combined with a two-pointer merge. The canonical building block for merge k sorted lists, the merge phase of Sort List, and any problem that assembles a new linked list node by node.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Merge k Sorted ListsMerge pairwise (divide and conquer) or push all heads into a min-heap; this two-list merge is the subroutine.
- Sort ListMerge sort a linked list: split at the middle, sort the halves, then merge — this is the merge step.
- Add Two NumbersSame dummy-node + tail building pattern, but summing digits with a carry instead of comparing.