A LeetCode 21, merging two sorted linked lists, reads as Easy on the surface, but in a live interview it exposes your boundary handling, pointer habits, and code cleanliness.

Many people finish in 3 minutes and then fail on these details: while condition written as || → null pointer cur forgetting to advance → linked list ends with only one node return dummy → result unexpectedly contains an extra -1

This problem isn't about whether you can solve it — it's about how cleanly you write it and whether you can survive follow-up questions. No filler in this piece; it breaks down the problem like a real interview, question by question.

---

✅ Understand the problem in 30 seconds Grasp the core idea "sorted → merge", confirm the boundaries first, then start writing

✅ Two solutions compared Iterative + sentinel node (interview first choice, O(1) space) Recursive (elegant, but O(m+n) stack depth risks stack overflow)

✅ 10 frequent pitfalls + self-check list Screenshot recommended, go through each item after you finish coding

✅ Two techniques that set you apart Comparator generalization + min-heap for k-way merge Jump directly from LeetCode 21 to LeetCode 23

✅ Interviewer's 9 follow-up questions + 30-second verbal template If you're prepared, they're easy points

✅ Self-assessment Excellent / Pass / Needs improvement — see which tier you're in

---

Who this is for: people grinding problems for autumn/spring jobs, students who always trip on linked lists, and candidates who want to move from "can AC" to "has engineering judgment".

At minimum you'll walk away with three things: An iterative template you can memorize A pitfall checklist A roadmap from LeetCode 21 → 88 → 23 → 148 for linked-list merging progression

---

Remember it in one sentence: Sentinel node handles the head, tail pointer pushes forward, remaining segment connects in one go, O(m+n) time, O(1) space.

---

If you find this useful, bookmark it first and follow the "198 Algorithm Problems" series, updated weekly.
Discussion today: What's the wildest pitfall you've hit on a linked-list problem? Did you create a cycle, or did you return dummy?

┌──────────────────────────────┐ │ Share in the comments │ The pitfall with the most likes gets a dedicated breakdown next issue │ 👇 Your failure story might save a job seeker this autumn └──────────────────────────────┘

---

LeetCode 21 Merging Two Sorted Linked Lists: Why Does an Easy Problem Filter Out Half the Candidates?

Last week I helped a friend run a mock interview and asked him to write LeetCode 21, "Merge Two Sorted Lists". The problem wasn't hard; he finished in three minutes — then I opened the code: the while condition was written as ||, causing a null pointer; cur wasn't advanced, leaving the list with only one node; and finally return dummy put an extra -1 in the result.

This problem is a mirror in interviews: the label says Easy, but the moment you start coding, your boundary handling, pointer habits, and code cleanliness are all exposed. Today I'll walk through the entire path — problem-solving approach, two solutions, pitfall checklist, and interview follow-up questions. If you're preparing for autumn/spring hiring, bookmark this; even veteran problem-solvers can use it as a self-check.

1. Read the problem: grab the key info in 30 seconds

Merge two ascending linked lists into a new ascending linked list and return it. The new list is made by splicing all the nodes from the two given lists.

Problem element	Key info
Input	Two non-decreasing singly linked lists l1, l2
Output	Head node of the merged, still-ordered linked list
Core constraint	Splice the original nodes directly, don't copy values or create new nodes
Data range	Node count [0, 50], node values [-100, 100], may be empty, may have duplicates

A few examples:

Input	Output
l1 = [1,2,4], l2 = [1,3,4]	[1,1,2,3,4,4]
l1 = [], l2 = []	[]
l1 = [], l2 = [0]	[0]

In an interview, don't rush to code. Proactively confirm three points with the interviewer — this immediately raises your standing:

"Let me confirm first: ① both lists are sorted, so two-pointer merge works; ② node count can be 0, so we handle empty lists; ③ the problem says 'splice all nodes', which I interpret as rearranging pointers in place, no new nodes needed, so space can be O(1)."

Just this sentence tells the interviewer you have engineering awareness.

2. Problem breakdown: what's the essence of this problem

In real development, we often encounter "merging two ordered data streams" scenarios — merging two ordered log streams, database merge queries, and the merge step of merge sort. This problem is essentially the linked-list version of the merge step in merge sort.

As an analogy: you have two stacks of playing cards, each already sorted. Each time you compare the top card of each stack, pull the smaller one onto a new pile, until one stack is empty, then just place the entire remaining stack on top.

Before writing code, think through three questions:

1. Both lists are sorted → naturally a merge scenario; scan with two pointers front to back, no need to re-sort;
2. The result head isn't known in advance → the head comes from l1 or l2 depending on the first comparison, so use a sentinel node to hold it and avoid special cases;
3. What to do when one list finishes → the rest of the other is already sorted, so splice the whole remaining segment at once, don't compare one-by-one.

Also note a basic data-structure fact: a singly linked list node = data field val + pointer field next; nodes are not contiguous in memory but linked by next, and you can only traverse forward — which is exactly why the merge must maintain a position pointer.

3. Solution 1: Iterative + sentinel node (first choice for interviews)

Core idea

Use a dummy node as the sentinel head, eliminating the hassle of checking the head node. Use a cur pointer that always points to the tail of the result list, traverse both original lists with two pointers, and append whichever is smaller. Finally, attach the entire unmatched segment directly to the tail.

One-sentence summary: attach whichever is smaller, then move forward.

Why do you need dummy?

Many people fail not on logic but on "which node to return". Without a sentinel, the result head is determined dynamically, and you'd have to add extra if (head == null) branches outside the loop to record the head, making the code ugly and error-prone.

The sentinel's role is to place a placeholder fake node in front of the real head, so that the "attach node" action is uniformly written as cur.next = xxx. At the end, just return dummy.next.

The essence of a sentinel node: use one meaningless leading node to swap out an entire boundary branch. Code volume and error rate both drop.

Merge process diagram

Taking l1=[1,2,4], l2=[1,3,4] as an example, the whole flow looks like this:

Look at the three-step fixed rhythm at the pointer level:

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, completely eliminate null-pointer special cases
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;              // cur always points to the tail of the result list

        // ② Two pointers traverse together, attach whichever is smaller
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {        // ③ Use <=; on equal values take l1 for stability
                cur.next = l1;
                l1 = l1.next;              // Advance the pointer of the selected list
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;                // ④ Advance the tail pointer
        }

        // ⑤ Splice the remaining segment all at once, no need to loop further
        cur.next = (l1 != null) ? l1 : l2;

        return dummy.next;                 // ⑥ dummy is just a tool; it never enters the result
    }
}

Four technical highlights of this code

Highlight	Explanation	Benefit
Sentinel node dummy	Fake head to unify all insertion logic	Eliminates "first insertion" special case; cuts branches in half
Splice remaining segment	cur.next = (l1 != null) ? l1 : l2	No need to handle tail inside the loop; don't use a loop for something O(1) does
Reuse nodes in place	Only modify next pointers, no new	Satisfies the "splice" requirement; O(1) space
<= preserves stability	On equal values, prefer l1	Equal-value nodes keep their relative order

Focus on the <= here: the difference of one equals sign demonstrates awareness of stable sorting. In production scenarios like multi-field sorting or merging log streams, stability is a hard requirement. When an interviewer sees you use <= and can explain why, it's a bright spot.

4. Solution 2: Recursion (elegant, but costs)

Core idea

Recursion thinks "what does this step do, and let the next level handle the rest": each time pick the smaller of the two head nodes, point its next to "the result of merging the remaining two lists", and recurse until one list is empty.

Break down the three essentials:

• Termination condition: l1 == null returns l2; l2 == null returns l1
• This-level logic: whichever head is smaller, its next points to "the result of merging the remaining part"
• Return: the current smaller node as the head of this level's result

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Recursion exit: if either list is empty, return the other directly
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        // Pick the smaller node, 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;
        }
    }
}

The elegance of recursion lies in "trust": I trust that mergeTwoLists(remaining part) will return a sorted list, so I only need to decide who is the current head — this is divide-and-conquer plus mathematical induction.

The whole expansion and backtracking process of the call stack:

The hidden engineering hazard of recursion: stack overflow

Time complexity is also O(m+n), each node processes no more than once. But space complexity is O(m+n) — the recursion depth equals the length of the merged list, and each call occupies a stack frame on the JVM stack.

Note: this isn't "extra array" space; it's call-stack space. The JVM default stack size is roughly 512KB to 1MB, each stack frame takes dozens to hundreds of bytes. When the list length reaches the 100k level, the recursive version crashes with StackOverflowError.

With node count ≤ 50, recursion has no real risk. But in production, or when list length is uncontrolled, iteration is the engineering default; recursion is a way to show clear thinking.

5. Comparison and selection of the two solutions

Dimension	Iterative (sentinel + tail-append)	Recursive
Time complexity	O(m+n) single pass	O(m+n) each level processes a node
Space complexity	O(1) in-place merge ✅	O(m+n) recursion stack overhead ⚠️
Code brevity	Moderate, logic straightforward	Minimal, core is 4 lines
Stack overflow risk	None ✅	Long lists will overflow 💥
Production readiness	First choice	Needs data-size assessment
Interview recommendation	⭐⭐⭐⭐⭐ standard answer	⭐⭐⭐ bonus supplement

Memorize the interview line directly:

"I'll write the iterative version first, O(1) space, no stack overflow risk, the engineering standard answer. I can also write recursion, more compact, but stack depth is O(m+n), risk of overflow with large data, so in production I pick iteration."

That shows both breadth and engineering judgment. This kind of "layered thinking" is worth more than AC itself.

6. Technical difficulties and pitfalls complete guide (highlight: screenshot this)

The table below is a collection of real mistakes from interview history, each paired with a specific solution:

#	Difficulty	Why it's easy to get wrong	Solution
1	Head node ownership uncertain	The result head comes from l1 or l2 depending on the first comparison; requires a pile of special cases	Introduce a sentinel dummy node; finally return dummy.next for one unified exit
2	Empty list / one short one long	Directly accessing l1.val throws NPE	while condition guarantees both are non-null; splice the whole remaining segment, which automatically handles single-empty and double-empty
3	Pointer order reversed → broken chain	Moving l1 before attaching the node, or taking l1.next before moving, loses nodes	Fixed sequence: attach cur.next → then advance l1 = l1.next → advance cur = cur.next; the three steps must not be swapped
4	Forgetting to move cur → overwrite/dead loop	Only moving cur inside one branch, next assignment overwrites the previous connection, list ends with one node	Put cur = cur.next uniformly at the end of the loop, not inside if/else
5	Wrong loop condition	Writing `while (l1 != null
6	Losing stability for equal values	Using < causes equal elements across lists to be out of order	Use <=, prefer l1 on equal
7	Habitually creating new nodes	Copying values to new nodes makes space O(n) and destroys original list	Modify pointers in place, reuse nodes; this is the key to O(1) space
8	Recursion stack overflow	Recursion depth = m+n; long lists overflow	Use iteration in production; if recursion is required, say "can be rewritten iteratively"
9	Accidentally creating a cycle	Using "head-insert" merge, wrong pointers produce a loop	Stick to tail-insert; never create data nodes
10	k-way extension times out	Merging k lists pairwise sequentially gives O(k·N) timeout	Use heap / divide-and-conquer to drop to O(N log k); see below

Plus a failed-interview self-check list; go through it after finishing your code:

• ❌ Dump values into an array, sort, and rebuild the linked list → space O(n), destroys original structure, shows no linked-list skill, direct penalty
• ❌ if (dummy = new ListNode(-1)) → assignment written as comparison, classic typo
• ❌ Missing cur = cur.next in the loop → result stuck at second node or infinite loop
• ❌ Access l1.val without null check → null pointer exception
• ❌ Returning dummy instead of dummy.next → result has an extra -1
• ❌ Writing a while loop after the main loop to move remaining nodes one by one → over-engineering

7. Two techniques to stand out

If your target is a big-company SSP, writing it correctly is not enough. The two code snippets below are what I recommend in interview coaching as "flex your muscles" moves.

Highlight 1: Comparator generalization — from "grinding algorithms" to "writing middleware"

Extract the "comparison rule" so object linked lists and reverse merges can reuse it:

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 thought: this person has abstraction awareness, not just memorizing solutions. A single Comparator parameter turns an algorithm problem into middleware-style code.

Highlight 2: k-way merge — priority queue version

This is the only correct way to jump from problem 21 to 23, and the sentinel code is reused unchanged:

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);   // put 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 joins the heap
    }
    return dummy.next;
}

Time complexity is O(N log k), where N is total node count.

8. Interviewer follow-up question set (prepare in advance, then they're free points)

Q1: Why use a sentinel node? Can you do without it?

Yes, but then you need an extra if (head == null) branch to record the head node. The sentinel's essence is to trade a little extra space for an entire boundary branch — shorter code, fewer mistakes.

Q2: Explain recursion's space complexity clearly.

Recursion depth equals m+n, one stack frame per level, space O(m+n). With a million-node list the recursive version crashes, so production uses iteration.

Q3: How to merge K sorted linked lists (LeetCode 23)?

Three approaches compared:

Approach	Idea	Time complexity	Evaluation
Sequential pairwise merge	Repeatedly call this problem's function	O(k·N)	Slow; times out on large data
Min-heap	Maintain the K current minimum nodes	O(N log k)	Recommended ✅
Divide-and-conquer pairwise merge	Merge in halves like merge sort	O(N log k)	Optimal, more memory-friendly

Q4: What if we need to dedupe after merging?

When l1.val == l2.val, attach one node and advance both pointers to skip the duplicate.

Q5: What if the lists are descending?

Two ways: ① reverse each list, merge, reverse back if needed; ② change the comparison to take the larger first, then reverse the whole result once.

Q6: What's the difference between merging two sorted arrays (LeetCode 88) and this problem?

Array version must fill from back to front to avoid overwriting unprocessed elements; linked list only changes pointers with no overwrite issue, so it goes front to back. Also, merge sort on arrays requires O(n) auxiliary array for merge, while on linked lists you modify pointers in place, bringing space down to O(1).

Q7: What if the original list cannot be modified and you can only use new nodes?

Then you can't modify pointers in place; you must new ListNode and copy values, degrading space to O(m+n).

Q8: How is linked-list merge sort (LeetCode 148) written?

Fast-slow pointer finds the middle → split → sort each half separately → call this problem's merge to combine. This problem is its foundation.

Q9: Is there a difference between singly and doubly linked lists for this problem?

Doubly linked list supports O(1) insertion at the tail and backward traversal; singly linked list relies on dummy + tail pointer to maintain the tail.

9. 30-second verbal template (memorize and use directly)

"This problem is essentially the merge step of merge sort. I use two pointers + sentinel node: dummy eliminates the head-node special case; in the loop, attach whichever is smaller, using <= for stability; after exiting the loop, splice the remaining segment directly because the original lists are already sorted. Time O(m+n), extra space O(1), in-place pointer rearrangement. There's also a recursive version, shorter but with O(m+n) stack depth, risk of overflow on large data, so in production I choose iteration. If extended to k-way, use a min-heap or divide-and-conquer, complexity O(N log k)."

After writing the code, proactively add a boundary analysis: "I noticed several edge cases: l1 empty, l2 empty, both empty, one short one long, equal values — the dummy + ternary operator approach handles all of them naturally." Don't wait for the interviewer to ask; speak up; it adds strong points.

Finally, here's the interviewer's grading perspective for self-assessment:

Grade	Performance
🟢 Excellent	Iterative version correct on first try + proactively mentions stability + can extend to k-way
🟡 Pass	Can write merge logic, but head handling is cumbersome
🔴 Needs improvement	Creates new nodes to splice / forgets dummy.next / creates a cycle

Final notes

The essence of this problem isn't code length, but three engineering mindsets: use dummy to eliminate edge branches, recognize "sorted → merge" as the algorithmic essence, and choose between iteration and recursion based on data scale. If only 3 minutes remain, submit the iterative version; if you have 10 minutes, also explain the evolution path through recursion and the min-heap.

One sentence to close: Sentinel node handles the head, tail pointer pushes forward, remaining segment connects in one go, O(m+n) time, O(1) space.

Related problems, recommended in order: LeetCode 21 (this problem) → LeetCode 88 Merge Sorted Array → LeetCode 23 Merge k Sorted Lists → LeetCode 148 Sort List, plus 剑指 Offer 25, and the linked-list merge line is complete.

If you found it useful, tap follow — the "198 Algorithm Problems" series updates weekly, from linked lists, binary trees, and dynamic programming to system design.

Two posts per week, more algorithm problems at: https://mp.weixin.qq.com/mp/appmsgalbum?__biz=Mzk5MDE0MDA3MA==&action=getalbum&album_id=4728642846076026883#wechat_redirect

Today's interaction: What's the wildest linked-list pitfall you've hit? Did you create a cycle, or return dummy? Share in the comments; the most-liked pitfall gets its own breakdown next issue.