Skip to content
LeetCode 21: Why This Easy Merge Lists Question Fails Half of Candidates
Fundamentals 28 min read

LeetCode 21: Why This Easy Merge Lists Question Fails Half of Candidates

This article provides a comprehensive guide to LeetCode 21 Merge Two Sorted Lists, covering iterative and recursive solutions, 10 common pitfalls with fixes, interview follow-up questions, and extensions to k-way merge, helping candidates move from merely passing to demonstrating engineering judgment.

Rain's Path to Java Mastery
Rain's Path to Java Mastery
Rain's Path to Java Mastery

Problem Overview: LeetCode 21 Merge Two Sorted Lists

Merge two ascending singly linked lists into a new ascending linked list by splicing the original nodes. Return the head of the merged list.

Key Information

Input: Two non-decreasing sorted singly linked lists l1, l2 Output: Head of the merged sorted linked list

Core Constraint: Directly splice original nodes; cannot copy values to create new nodes

Data Range: Node count [0, 50], node values [-100, 100], lists may be empty, may have duplicate values

Examples

l1 = [1,2,4]

, l2 = [1,3,4] →

[1,1,2,3,4,4]
l1 = []

, l2 = [] →

[]
l1 = []

, l2 = [0] →

[0]

Pre-Coding Confirmation (Engineering Awareness)

"I'll confirm: ① Both lists are sorted, so two-pointer merge applies; ② Node count may be 0, must handle empty lists; ③ 'Splice all nodes' means in-place pointer rearrangement , no new nodes needed, space can be O(1)."

Problem Essence

Real-world scenarios: merging two sorted log streams, database merge queries, merge step of merge sort. This problem is essentially the merge step of merge sort adapted to linked lists .

Analogy: You have two sorted decks of cards. Repeatedly compare the top cards, move the smaller to a new pile. When one deck empties, attach the rest of the other deck.

Three Clarifying Questions

Both lists sorted → natural merge scenario, two pointers scan forward, no re-sorting needed.

Result head uncertain → head comes from l1 or l2 depending on first comparison, use a sentinel node to avoid special cases.

One list finishes early → the remainder is already sorted, attach the whole segment at once , no further comparisons.

Data structure reminder: singly-linked node = val + next pointer, nodes non-contiguous in memory, linked by next, traversal only forward — hence must preserve position pointers during merge.

Solution 1: Iterative + Sentinel Node (Interview Preferred)

Core Idea

Use a dummy node as sentinel head to eliminate head-null checks; use cur pointer always pointing to the tail of the result list. Two pointers traverse both lists simultaneously, attach the smaller node; finally attach the remaining list in one go.

One-liner: Attach smaller, then advance .

Why Dummy Node?

Many fail not on logic but on "which node to return". Without sentinel, the result head is dynamically determined, requiring an extra if (head == null) branch outside the loop — ugly and error-prone.

The sentinel places a placeholder before the real head (like a dummy person holding the front of a queue), making every insertion uniform: cur.next = xxx, finally return dummy.next.

Sentinel essence: trade one meaningless node for an entire boundary branch. Code size and error rate both drop.

Merge Process Illustration

Example l1=[1,2,4], l2=[1,3,4]:

Merge process illustration
Merge process illustration

Pointer-level three-step rhythm:

Pointer rhythm illustration
Pointer rhythm illustration

Core Code (Java)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // ① Sentinel node: unify head logic, eliminate null checks
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy; // cur always points to result tail

        // ② Two pointers traverse together, attach smaller
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) { // ③ Use <=, equal takes l1, ensures stability
                cur.next = l1;
                l1 = l1.next; // ④ Chosen list pointer advances
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next; // ⑤ Tail pointer advances in sync
        }

        // ⑥ Remaining segment attached in one go, no more loop
        cur.next = (l1 != null) ? l1 : l2;

        // ⑦ Dummy is just a tool, not part of result
        return dummy.next;
    }
}

Four Technical Highlights

Sentinel dummy : Fake head unifies all insertion logic → Eliminates "first insertion" special case, halves branches

Attach remainder in one go : cur.next = (l1 != null) ? l1 : l2 → Loop doesn't handle cleanup, don't use loop for O(1) work

In-place node reuse : Only rewire next pointers, no new → Meets "splice" requirement, space O(1)

&lt;= for stability : Equal values prefer l1 → Relative order of equal nodes preserved

The <= matters: a single equal sign reflects stable sort awareness. In production (multi-field sort, log merging), stability is a hard requirement. Interviewers notice when you use <= and can explain why.

Solution 2: Recursive (Elegant but Costly)

Core Idea

Recursive mindset: "Do current step, delegate the rest": pick the smaller head, let its next point to "merge of the remaining two lists", recurse until one list is null.

Three Elements

Base case : l1 == null return l2; l2 == null return l1.

Current logic : smaller head's next points to "merge of remaining parts".

Return : current smaller node as head of this level's result.

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Base case: either list empty, return the other
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        // Pick smaller, recursively merge the rest
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

Recursion's elegance lies in "trust": I trust mergeTwoLists(remaining) returns a sorted list, so I only decide who is the current head — this is divide-and-conquer + mathematical induction.

Call Stack Expansion and Backtracking

Recursive call stack illustration
Recursive call stack illustration

Hidden Engineering Risk: Stack Overflow

Time complexity also O(m+n), each node processed once. But space complexity is O(m+n) — recursion depth equals merged list length, each call consumes a JVM stack frame.

Note: This is not "extra array" space, it's call stack space. JVM default stack ~512KB-1MB, each frame tens to hundreds of bytes. At 100k nodes, recursive version throws StackOverflowError .

Problem constraints: nodes ≤ 50, recursion safe here. But in production or unbounded length, iterative is the engineering default , recursion only demonstrates clear thinking.

Comparison & Selection

Time Complexity : Both O(m+n) single pass

Space Complexity : Iterative O(1) in-place ✅; Recursive O(m+n) recursion stack ⚠️

Code Conciseness : Iterative medium, intuitive; Recursive minimal, core 4 lines

Stack Overflow Risk : Iterative none ✅; Recursive long lists crash 💥

Production Viability : Iterative preferred; Recursive must assess data scale

Interview Recommendation : Iterative ⭐⭐⭐⭐⭐ standard answer; Recursive ⭐⭐⭐ bonus supplement

Interview Script to Memorize

"I'll write iterative first: O(1) space, no stack overflow, engineering standard. I can also write recursive — shorter code but O(m+n) stack depth, risk of overflow on large data, so production I choose iterative."

Shows breadth and engineering judgment. This "layered thinking" is worth more than just AC.

Technical Pitfalls & Anti-Pitfall Checklist

Below list summarizes real interview failures, each with a fix:

Head ownership uncertain → Result head from l1 or l2 depends on first compare, needs many special cases → Fix: Introduce sentinel dummy, finally return dummy.next unifies exit

Empty list / one long one short → Direct l1.val access throws NPE → Fix: while condition ensures both non-null; remainder attached in one go, auto-handles single/double empty

Pointer order wrong → broken chain → Advance l1 before linking, or read l1.next before advancing, loses nodes → Fix: Fixed routine: link first cur.next → then advance l1 = l1.next → then move cur = cur.next, order immutable

Forget to move cur → overwrite/infinite loop → Only move cur in one branch, next assignment overwrites previous link, list ends up with one node → Fix: cur = cur.next placed at loop end, not inside if/else

Loop condition wrong → Write while (l1 != null || l2 != null), loop body full of null checks, long and NPE-prone → Fix: Standard uses &&, delegate "one list exhausted" to post-loop one-liner

Equal-value stability lost → Using < causes equal elements across lists to reorder → Fix: Use <=, equal prefers l1

Habitual new node creation → Copy values to new nodes, space becomes O(n) and breaks original structure → Fix: In-place pointer rewrite, key to O(1) space

Recursive stack overflow → Recursion depth = m+n, long lists crash → Fix: Production use iterative; if recursion required, state "can rewrite as iterative"

Accidentally create cycle → Using "head insertion" merges, pointer mis-wiring creates cycle infinite loop → Fix: Stick to tail insertion, never new data nodes

K-way extension times out → Sequentially merging k lists pairwise, O(k·N) TLE → Fix: Heap / divide-and-conquer to O(N log k), see below

Post-Code Self-Check Checklist

❌ Dump values into array, sort, rebuild list → O(n) space, destroys structure, shows no linked-list skill, instant deduction.

❌ if (dummy = new ListNode(-1)) → assignment written as condition, classic typo.

❌ Loop missing cur = cur.next → result stuck at second node or infinite loop.

❌ Access l1.val without null check → NPE.

❌ Return dummy instead of dummy.next → result gains an extra -1.

❌ After loop, write another while to move remaining nodes one by one → redundant.

Two Differentiating Advanced Techniques

Highlight 1: Comparator Generalization — From "Algorithm Drill" to "Middleware"

Extract "comparison rule" for reuse on object lists, descending merge, etc.:

public static ListNode merge(ListNode a, ListNode b, Comparator<ListNode> cmp) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while (a != null && b != null) {
        if (cmp.compare(a, b) <= 0) { tail.next = a; a = a.next; }
        else { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;
    return dummy.next;
}
Interviewer's inner monologue: This person has abstraction awareness, not a pattern memorizer. One Comparator parameter turns an algorithm problem into middleware flavor.

Highlight 2: K-Way Merge — Priority Queue Version

This is the only correct leap from LC21 to LC23 , sentinel pattern reused verbatim:

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq =
    new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
    for (ListNode h : lists) if (h != null) pq.offer(h); // k heads into heap

    ListNode dummy = new ListNode(0), tail = dummy;
    while (!pq.isEmpty()) {
        ListNode cur = pq.poll();
        tail.next = cur;
        tail = cur;
        if (cur.next != null) pq.offer(cur.next); // successor replenishes
    }
    return dummy.next;
}

Time complexity O(N log k), N = total nodes.

Interview Follow-up Set (Prepare Early, Asked = Free Points)

Q1: Why sentinel? Can't do without?

Possible, but need extra if (head == null) branch to record head. Sentinel trades tiny space for an entire boundary branch — shorter, less error-prone.

Q2: Explain recursive space complexity.

Depth = m+n, one stack frame per level, space O(m+n). Million-node lists crash recursion, so production uses iterative.

Q3: Merge K sorted lists (LC23) how?

Three approaches compared:

Sequential pairwise merge : Repeatedly call LC21 function → O(k·N) → Slow, TLE on large data

Min-heap : Maintain k current smallest nodes → O(N log k) → Recommended ✅

Divide-and-conquer pairwise : Merge like merge sort, halve each round → O(N log k) → Optimal, memory-friendlier

Q4: Need deduplication after merge?

When l1.val == l2.val, attach one node, advance both pointers, skip duplicates.

Q5: Lists are descending?

Two paths: ① Reverse each then merge, reverse back if needed; ② Flip comparison to pick larger first, then reverse whole result once.

Q6: Difference from merging two sorted arrays (LC88)?

Array version fills backward to avoid overwriting unprocessed elements; linked list only rewires pointers, no overwrite issue, forward merge works. Also array merge needs O(n) auxiliary array, linked list does in-place pointer rewrite, space drops to O(1).

Q7: Original lists immutable, must use new nodes?

Then cannot rewire in-place, must new ListNode copy values, space degrades to O(m+n).

Q8: Linked list merge sort (LC148) how?

Fast-slow pointers find middle → split → recursively sort → call LC21 merge. This problem is its foundation.

Q9: Singly vs doubly linked list difference here?

Doubly linked allows O(1) tail insertion, reverse traversal; singly linked relies on dummy + tail to maintain tail pointer.

30-Second Verbal Template (Memorize & Use)

"This problem is essentially the merge step of merge sort. I use two pointers + sentinel node : dummy eliminates head special case, loop attaches smaller, &lt;= ensures stability; after loop, remaining segment attached wholesale because original lists are sorted. Time O(m+n), extra space O(1), in-place rearrangement. Recursive version exists — shorter code but O(m+n) stack depth, overflow risk on large data, so engineering choice is iterative. For k-way extension, I'd use min-heap or divide-and-conquer, O(N log k)."

After coding, proactively add boundary analysis: "I've covered edge cases: l1 empty, l2 empty, both empty, unequal lengths, equal values — dummy + ternary operator handles all naturally." Don't wait for interviewer to ask; volunteer it, likability maxed.

Interviewer's Rating Perspective for Self-Assessment

🟢 Excellent : Iterative correct first try + proactive stability mention + can extend to k-way

🟡 Pass : Can write merge logic but head handling verbose

🔴 Needs Improvement : Creates new nodes / forgets dummy.next / creates cycle

Closing

The essence of this problem isn't code length, but three engineering mindsets: use dummy to kill boundary branches, recognize "sorted → merge" algorithmic essence, choose between iterative and recursive based on data scale . If only 3 minutes left, submit iterative; if 10 minutes, present recursive and min-heap evolution path.

One-liner summary: Sentinel guards head, tail pointer advances, remainder attached in one go, O(m+n) time, O(1) space.

Related problems in suggested order: LeetCode 21 (this) → LeetCode 88 Merge Sorted Array → LeetCode 23 Merge k Sorted Lists → LeetCode 148 Sort List, plus 剑指 Offer 25 — completes the linked-list merge progression.

Original Source

Signed-in readers can open the original source through BestHub's protected redirect.

Sign in to view source
Republication Notice

This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactadmin@besthub.devand we will review it promptly.

interview preparationLinked ListRecursive AlgorithmK-way MergeAlgorithm PitfallsIterative AlgorithmLeetCode 21Merge Two Sorted Lists
Reader feedback

How this landed with the community

Sign in to like

Rate this article

Was this worth your time?

Sign in to rate
Discussion

0 Comments

Thoughtful readers leave field notes, pushback, and hard-won operational detail here.