Loading…

easyLinked ListsLC #21Asked very often

Merge Two Sorted Lists

Q: How do you solve Merge Two Sorted Lists using the Iterative — Dummy Node + Tail Splice (Optimal) approach?

When to use it: Lead with this. The dummy node is the idiom interviewers want to see for list construction. 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 write `if (head == null) head = node; else tail.next = node;`. A dummy node is a fake node placed before the real head. Now `tail` always has a valid `.next` to write, including the very first append — one uniform code path, zero edge cases. At the end the real list starts at `dummy.next`. **The merge loop.** While both lists have nodes, compare `l1.val` and `l2.val`, splice the smaller node onto `tail.next`, advance that list's pointer, and move `tail` forward onto the node we just attached. Using `<=` means equal values take from `l1` first, keeping the merge stable. **Why the leftover splice works in O(1).** The loop exits the moment *one* list empties. The other list is non-empty and, critically, already sorted and entirely ≥ everything we've appended (because we always took the smallest available). So we don't iterate it — we just point `tail.next` at its head and the whole tail comes along for free. **Why we splice, not copy.** We rewire `next` pointers of the original nodes rather than allocating new ones. That's what keeps space at O(1); the problem even says 'splicing together the nodes'. Time complexity: O(n + m). Space complexity: O(1).

Q: How do you solve Merge Two Sorted Lists using the Recursive — Pick Smaller Head, Recurse on the Rest approach?

When to use it: A clean alternative to mention; flag the O(n + m) call-stack cost versus the iterative O(1). 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 must come next. We set `list1.next = merge(list1.next, list2)` — recursively merging the rest of list1 with all of list2 — and return `list1` as the head of this subproblem's answer. 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. With the tiny constraints here (≤ 50 nodes each) that's irrelevant, but on long lists the iterative O(1)-space version avoids any stack-overflow risk — which is why it's the safer lead. Time complexity: O(n + m). Space complexity: O(n + m).

LCPractice

Linked List · 3 of 24 · 8 min

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

In plain English

Both inputs are already sorted ascending. We weave their nodes together so the result is one ascending list, reusing the existing nodes (splicing links) rather than creating new ones. Either or both inputs may be empty.

Examples

Example 1

Input: list1 = [1, 2, 4], list2 = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]
Note: Interleave by value: 1(l1), 1(l2), 2, 3, then 4(l1), 4(l2).

Example 2

Input: list1 = [], list2 = []
Output: []
Note: Both empty — the loop never runs and dummy.next is null.

Example 3

Input: list1 = [], list2 = [0]
Output: [0]
Note: list1 is empty, so the whole of list2 is spliced on after the (empty) loop.

Constraints

The number of nodes in both lists is in the range [0, 50]
-100 ≤ Node.val ≤ 100
Both list1 and list2 are sorted in non-decreasing order

Clarifying questions4First question: Are both input lists guaranteed sorted in non-decreasing order?Explore questions

Q1.Are both input lists guaranteed sorted in non-decreasing order?
Yes — that's the precondition that lets us merge in a single linear pass. If they weren't, we'd have to sort first.
Q2.Can I reuse the existing nodes or must I allocate new ones?
Splicing the existing nodes is expected and gives O(1) extra space. Allocating copies would be O(n) memory for no benefit.
Q3.What should happen if one or both lists are empty?
If one is empty, return the other; if both are empty, return null. The dummy-node approach handles this without special branches.
Q4.How should ties (equal values) be ordered?
Either order is sorted, but I'll take from list1 on ties (using <=) to keep the merge stable and predictable.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Splice the two sorted lists into one by repeatedly attaching the smaller current node. Use a dummy head node so you never special-case the first append, and keep a tail pointer that you advance after each splice. When one list runs out, attach the entire remainder of the other in O(1). O(n + m) time, O(1) space — no new nodes are allocated, only links are rewired.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reach for a dummy head to avoid head-initialization edge cases, and whether you finish by splicing the leftover list in O(1) rather than node-by-node.

Where candidates slip

Not using a dummy node and writing tangled first-node logic, or forgetting to attach the remaining list after the loop ends.

How to stand out

Use the dummy node, return dummy.next, splice the remainder in one assignment, and mention 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.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Iterative — Dummy Node + Tail Splice (Optimal)Optimal	`O(n + m)`	`O(1)`	Lead with this. The dummy node is the idiom interviewers want to see for list construction.	Read
2	Recursive — Pick Smaller Head, Recurse on the Rest	`O(n + m)`	`O(n + m)`	A clean alternative to mention; flag the O(n + m) call-stack cost versus the iterative O(1).	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewMerge two sorted listsNeed O(1) space?YesNo / prefer recursionExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Iterative — Dummy Node + Tail Splice (Optimal)

TimeO(n + m)SpaceO(1)

Lead with this. The dummy node is the idiom interviewers want to see for list construction.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You're building a new chain whose head you don't know until you compare the first two values. What if you had a fake node sitting in front of the real head so the first append looks like every other append?

2Hint 2Explore hint

Keep a tail pointer starting at the dummy. Each step, compare l1.val and l2.val, splice the smaller node onto tail.next, advance that list, then advance tail.

3Hint 3Explore hint

When one list is exhausted, the other is already sorted — set tail.next to whichever list still has nodes, in one assignment. 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 write if (head == null) head = node; else tail.next = node;. A dummy node is a fake node placed before the real head. Now tail always has a valid .next to write, including the very first append — one uniform code path, zero edge cases. At the end the real list starts at dummy.next.

The merge loop. While both lists have nodes, compare l1.val and l2.val, splice the smaller node onto tail.next, advance that list's pointer, and move tail forward onto the node we just attached. Using <= means equal values take from l1 first, keeping the merge stable.

Why the leftover splice works in O(1). The loop exits the moment one list empties. The other list is non-empty and, critically, already sorted and entirely ≥ everything we've appended (because we always took the smallest available). So we don't iterate it — we just point tail.next at its head and the whole tail comes along for free.

Why we splice, not copy. We rewire next pointers of the original nodes rather than allocating new ones. That's what keeps space at O(1); the problem even says 'splicing together the 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

[0]

tail ↓

[1]

Current pointerResolved stateNot processed

Final result[1, 1, 2, 3, 4]

C · Code with teaching comments

solution.javaJava

Iterative — Dummy Node + Tail Splice (Optimal) — optimal

6 teaching notes

1
public class ListNode {
2
    int val;
3
    ListNode next;
4
    ListNode() {}
5
    ListNode(int val) { this.val = val; }
6
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
7
}
8
 
9
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
10
    // Sentinel placed before the real head so the first append needs no special case.
11
    ListNode dummy = new ListNode();
12
    // Always points at the last node of the merged list; we append to tail.next.
13
    ListNode tail = dummy;
14
    while (list1 != null && list2 != null) {
15
        // <= keeps the merge stable: equal values take from list1 first.
16
        if (list1.val <= list2.val) {
17
            tail.next = list1;
18
            list1 = list1.next;
19
        } else {
20
            tail.next = list2;
21
            list2 = list2.next;
22
        }
23
        // Advance tail onto the node we just spliced so the next append goes after it.
24
        tail = tail.next;
25
    }
26
    // One list is empty; attach the entire sorted remainder of the other in O(1).
27
    tail.next = (list1 != null) ? list1 : list2;
28
    // Skip the throwaway dummy and return the real head.
29
    return dummy.next;
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(n + m) timeO(1) spaceOpen the invariant and proofExplore the proof

A dummy head turns 'build a list' into a branch-free loop, and the 'attach the rest in one link' trick exploits the fact that a sorted remainder needs no further work. These two moves together 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 a single O(1) link. Only a dummy node and a tail pointer are used → O(1) extra space.

E · Edge cases and pitfalls6list1 = [], list2 = [] — Loop body never runs; tail.next = null; return dummy.next = null.Explore 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), then 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) memory.

03.2

Approach 2 of 2

Recursive — Pick Smaller Head, Recurse on the Rest

TimeO(n + m)SpaceO(n + m)

A clean alternative to mention; flag the O(n + m) call-stack cost versus the iterative O(1).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you knew the merge of the two tails, how would you build the full answer? You'd just attach the smaller head in front of it.

2Hint 2Explore hint

Base cases: if either list is null, the merged result is simply the other list.

3Hint 3Explore 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 must come next. We set list1.next = merge(list1.next, list2) — recursively merging the rest of list1 with all of list2 — and return list1 as the head of this subproblem's answer. 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. With the tiny constraints here (≤ 50 nodes each) that's irrelevant, but on long lists 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]

merge([1,2],[1,3])

1<=1 → head=l1(1); recurse([2],[1,3])

Statehead 1(l1)

Final result[1, 1, 2, 3]

C · Code with teaching comments

Reference implementation previewpublic ListNode mergeTwoLists(ListNode list1, ListNode list2) { if (list1 == null) return list2; if (list2 == null) return list1; if (list1.val <= list2.val) { list1.next = mergeTwoLists(list1.next, list2);Explore the full code

solution.javaJava

Recursive — Pick Smaller Head, Recurse on the Rest — reference

4 teaching notes

1
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
2
    // Base case: nothing left in list1, so the rest is just list2.
3
    if (list1 == null) return list2;
4
    if (list2 == null) return list1;
5
    // list1's head is the smallest unused node, so it leads this subproblem.
6
    if (list1.val <= list2.val) {
7
        // Recursively merge the remainder and hang it off the chosen head.
8
        list1.next = mergeTwoLists(list1.next, list2);
9
        // Return the chosen smaller head as this call's merged head.
10
        return list1;
11
    } else {
12
        list2.next = mergeTwoLists(list1, list2.next);
13
        return list2;
14
    }
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n + m) timeO(n + m) spaceOpen the invariant and proofExplore 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 there are n + m calls total → O(n + m) time. The recursion depth equals the number of nodes, giving O(n + m) stack space.

E · Edge cases and pitfalls3Forgetting a base case — infinite recursion or a null dereference.Explore 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 playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

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.

Explore the code comparison

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;

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.

Explore the code comparison

Don't write this

tail.next = list1 if list1 else list2
return dummy   # bogus leading node

Write this instead

tail.next = list1 if list1 else list2
return dummy.next

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Dummy node + tail pointer merge (two-pointer splice)

Code pattern to memorize

dummy = ListNode()
tail = dummy
while l1 and l2:
    if l1.val <= l2.val: tail.next = l1; l1 = l1.next
    else: tail.next = l2; l2 = l2.next
    tail = tail.next
tail.next = l1 if l1 else l2
return dummy.next

Rules to remember

1Use a dummy head so the first node attaches with the same code as every other — no if head == null branch.
2Return dummy.next, never dummy itself — dummy is a throwaway sentinel.
3After the loop, attach the remaining list wholesale: tail.next = l1 or l2 — it's already sorted, so one link finishes it.
4Use <= (not <) when comparing to keep the merge stable for equal values; either is correct, <= is conventional.
5Splice existing nodes — don't allocate new ones — to keep it O(1) space.

Use this pattern when

Merge two (or, by extension, k) already-sorted linked lists
The merge step of merge sort on a linked list
Combining sorted streams where random access is unavailable
Any 'interleave two ordered sequences' problem on pointer-based data

Choose another pattern when

Inputs are arrays with random access → a simple index-based merge or library sort may be simpler
You need to merge many lists at once → use a min-heap (Merge k Sorted Lists), not pairwise splicing in a loop without care
Lists are unsorted → sort first; this technique assumes sorted inputs

Interview takeaway

The dummy-node + tail pattern removes every 'is this the first node?' edge case from linked-list building. 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

Same pattern

←

Linked List Cycle Detection

Continue · Next problem

Reorder List

easyLinked ListsLC #21Asked very often

Merge Two Sorted Lists

LCPractice

Linked List · 3 of 24 · 8 min

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

In plain English

Examples

Example 1

Input: list1 = [1, 2, 4], list2 = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]
Note: Interleave by value: 1(l1), 1(l2), 2, 3, then 4(l1), 4(l2).

Example 2

Input: list1 = [], list2 = []
Output: []
Note: Both empty — the loop never runs and dummy.next is null.

Example 3

Input: list1 = [], list2 = [0]
Output: [0]
Note: list1 is empty, so the whole of list2 is spliced on after the (empty) loop.

Constraints

The number of nodes in both lists is in the range [0, 50]
-100 ≤ Node.val ≤ 100
Both list1 and list2 are sorted in non-decreasing order

Clarifying questions4First question: Are both input lists guaranteed sorted in non-decreasing order?Explore questions

Q1.Are both input lists guaranteed sorted in non-decreasing order?
Yes — that's the precondition that lets us merge in a single linear pass. If they weren't, we'd have to sort first.
Q2.Can I reuse the existing nodes or must I allocate new ones?
Splicing the existing nodes is expected and gives O(1) extra space. Allocating copies would be O(n) memory for no benefit.
Q3.What should happen if one or both lists are empty?
If one is empty, return the other; if both are empty, return null. The dummy-node approach handles this without special branches.
Q4.How should ties (equal values) be ordered?
Either order is sorted, but I'll take from list1 on ties (using <=) to keep the merge stable and predictable.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you reach for a dummy head to avoid head-initialization edge cases, and whether you finish by splicing the leftover list in O(1) rather than node-by-node.

Where candidates slip

Not using a dummy node and writing tangled first-node logic, or forgetting to attach the remaining list after the loop ends.

How to stand out

Use the dummy node, return dummy.next, splice the remainder in one assignment, and mention 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.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Iterative — Dummy Node + Tail Splice (Optimal)Optimal	`O(n + m)`	`O(1)`	Lead with this. The dummy node is the idiom interviewers want to see for list construction.	Read
2	Recursive — Pick Smaller Head, Recurse on the Rest	`O(n + m)`	`O(n + m)`	A clean alternative to mention; flag the O(n + m) call-stack cost versus the iterative O(1).	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2 · Optimal

Iterative — Dummy Node + Tail Splice (Optimal)

TimeO(n + m)SpaceO(1)

Lead with this. The dummy node is the idiom interviewers want to see for list construction.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

2Hint 2Explore hint

Keep a tail pointer starting at the dummy. Each step, compare l1.val and l2.val, splice the smaller node onto tail.next, advance that list, then advance tail.

3Hint 3Explore hint

When one list is exhausted, the other is already sorted — set tail.next to whichever list still has nodes, in one assignment. 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 we splice, not copy. We rewire next pointers of the original nodes rather than allocating new ones. That's what keeps space at O(1); the problem even says 'splicing together the 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

[0]

tail ↓

[1]

Current pointerResolved stateNot processed

Final result[1, 1, 2, 3, 4]

C · Code with teaching comments

solution.javaJava

Iterative — Dummy Node + Tail Splice (Optimal) — optimal

6 teaching notes

1
public class ListNode {
2
    int val;
3
    ListNode next;
4
    ListNode() {}
5
    ListNode(int val) { this.val = val; }
6
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
7
}
8
 
9
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
10
    // Sentinel placed before the real head so the first append needs no special case.
11
    ListNode dummy = new ListNode();
12
    // Always points at the last node of the merged list; we append to tail.next.
13
    ListNode tail = dummy;
14
    while (list1 != null && list2 != null) {
15
        // <= keeps the merge stable: equal values take from list1 first.
16
        if (list1.val <= list2.val) {
17
            tail.next = list1;
18
            list1 = list1.next;
19
        } else {
20
            tail.next = list2;
21
            list2 = list2.next;
22
        }
23
        // Advance tail onto the node we just spliced so the next append goes after it.
24
        tail = tail.next;
25
    }
26
    // One list is empty; attach the entire sorted remainder of the other in O(1).
27
    tail.next = (list1 != null) ? list1 : list2;
28
    // Skip the throwaway dummy and return the real head.
29
    return dummy.next;
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(n + m) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6list1 = [], list2 = [] — Loop body never runs; tail.next = null; return dummy.next = null.Explore 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), then 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) memory.

03.2

Approach 2 of 2

Recursive — Pick Smaller Head, Recurse on the Rest

TimeO(n + m)SpaceO(n + m)

A clean alternative to mention; flag the O(n + m) call-stack cost versus the iterative O(1).

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

If you knew the merge of the two tails, how would you build the full answer? You'd just attach the smaller head in front of it.

2Hint 2Explore hint

Base cases: if either list is null, the merged result is simply the other list.

3Hint 3Explore 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.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

list1 = [1, 2], list2 = [1, 3]

merge([1,2],[1,3])

1<=1 → head=l1(1); recurse([2],[1,3])

Statehead 1(l1)

Final result[1, 1, 2, 3]

C · Code with teaching comments

solution.javaJava

Recursive — Pick Smaller Head, Recurse on the Rest — reference

4 teaching notes

1
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
2
    // Base case: nothing left in list1, so the rest is just list2.
3
    if (list1 == null) return list2;
4
    if (list2 == null) return list1;
5
    // list1's head is the smallest unused node, so it leads this subproblem.
6
    if (list1.val <= list2.val) {
7
        // Recursively merge the remainder and hang it off the chosen head.
8
        list1.next = mergeTwoLists(list1.next, list2);
9
        // Return the chosen smaller head as this call's merged head.
10
        return list1;
11
    } else {
12
        list2.next = mergeTwoLists(list1, list2.next);
13
        return list2;
14
    }
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n + m) timeO(n + m) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Forgetting a base case — infinite recursion or a null dereference.Explore 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 playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

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.

Explore the code comparison

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;

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.

Explore the code comparison

Don't write this

tail.next = list1 if list1 else list2
return dummy   # bogus leading node

Write this instead

tail.next = list1 if list1 else list2
return dummy.next

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Dummy node + tail pointer merge (two-pointer splice)

Code pattern to memorize

dummy = ListNode()
tail = dummy
while l1 and l2:
    if l1.val <= l2.val: tail.next = l1; l1 = l1.next
    else: tail.next = l2; l2 = l2.next
    tail = tail.next
tail.next = l1 if l1 else l2
return dummy.next

Rules to remember

1Use a dummy head so the first node attaches with the same code as every other — no if head == null branch.
2Return dummy.next, never dummy itself — dummy is a throwaway sentinel.
3After the loop, attach the remaining list wholesale: tail.next = l1 or l2 — it's already sorted, so one link finishes it.
4Use <= (not <) when comparing to keep the merge stable for equal values; either is correct, <= is conventional.
5Splice existing nodes — don't allocate new ones — to keep it O(1) space.

Use this pattern when

Merge two (or, by extension, k) already-sorted linked lists
The merge step of merge sort on a linked list
Combining sorted streams where random access is unavailable
Any 'interleave two ordered sequences' problem on pointer-based data

Choose another pattern when

Inputs are arrays with random access → a simple index-based merge or library sort may be simpler
You need to merge many lists at once → use a min-heap (Merge k Sorted Lists), not pairwise splicing in a loop without care
Lists are unsorted → sort first; this technique assumes sorted inputs

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Linked List Cycle Detection

Continue · Next problem

Reorder List