LeetCode 21 merges two ordered linked lists. It is an Easy interview question, but it is a touchstone for testing the basic skills of linked lists. This article explains in detail the two options of Sentinel iteration (O(1) in-situ merge) and recursion, sorting out 10 frequently encountered pitfalls. It comes with high-frequency questioning by interviewers and oral templates. It extends the generalization of Comparator and realizes K-way merging with small top stacks. It opens up the 21→88→23→148 linked list merging learning route. It is suitable for developers who are preparing for autumn recruitment and polishing their engineering thinking. Pay attention to the continuous updates of the algorithm series!
A LeetCode 21, with easy questions, can reveal your boundary handling, pointer habits and code cleanliness on the spot.
Many people finish writing in 3 minutes and then get hung up on these details:
whileThe condition is written as||→ null pointercurForget and move → There is only one node left in the linked listreturn dummy→ As a result, more appeared out of thin air-1This question is not “can you do it?”, but “whether you can write it cleanly, and whether you can handle it and ask questions.”
This article is not meant to be watery, but a one-stop breakdown based on actual interviews:
✅ 30 seconds to solve the question
Grasp the essence of “orderly → merge” and confirm the boundaries first before taking action.
✅ Comparison of two solutions
Iteration + sentinel node (preferred for interviews, O(1) space)
Recursion (elegant, but O(m+n) stack depth has the risk of stack explosion)
✅ 10 Frequent Pitfalls + Self-Check Checklist
Suggested screenshotsgo through the code one by one after writing it.
✅ Two ways of writing that widen the gap
Comparator generalization + small vertex k-way merging
Jump directly from LeetCode 21 to 23
✅ Interviewer 9 consecutive questions + 30 seconds dictation template
When asked, points are given.
✅ self-assessment rating
Excellent/Qualified/Needing improvement, see which level you are in
Suitable for whom: We recruit people who write questions in the fall and recruit in spring, students who always overturn their linked lists, and interviewees who want to advance from “knowing AC” to “having engineering judgment”.
Take away at least three things after reading：
A set of iterative templates that can be memorized
A pitfall list
a piece from LeetCode 21 → 88 → 23 → 148 Advanced route of linked list merging
One sentence to remember:
The sentinel node covers the head, and the tail pointer is pushed back, leaving a section that is connected, O(m+n) time, O(1) space.
Collect first if you find it usefulpay attention to the “Algorithm 198 Questions” series, updated every week.
Today’s interaction: What’s the most outrageous pitfall you’ve ever encountered on a linked list? Created a ring, or return Got it dummy？
┌──────────────────────────────┐
│ Chat in the comment area
│ The pit with the most likes, I will write a special article to dismantle it in the next issue
│ 👇 Your overturning experience may save someone in Qiuzhao
└──────────────────────────────┘
Last week, I helped a friend simulate an interview and asked him to write LeetCode 21 “Merge Two Ordered Linked Lists”. The question was not difficult, he finished it in three minutes – then I opened the code and took a look:while The condition is written as || resulting in a null pointer,cur Forgetting to move back leads to only one node left in the linked list, and finally return dummy The result was an extra -1 out of thin air.
This question is the “demon mirror” in the interview: the question is easy, but once you do it, boundary processing, pointer habits, and code cleanliness are all exposed. Today I will give a thorough explanation of this question from the idea of solving the question, the two solutions, the list of pitfalls to the interviewer’s follow-up questions. Students who are preparing for autumn recruitment and spring recruitment are recommended to save it, and veterans of answering questions can also check it for themselves.
1. Read the question first: Seize the key information in 30 seconds
put twoAscending orderLinked lists are merged into a new oneAscending orderlinked list and return. The new linked list is passedSplicingGiven two linked lists composed of all nodes.
| question elements | key information |
|---|---|
| enter | twonon-decreasingsorted singly linked list l1、l2 |
| output | The head node of the new linked list that is still in order after merging |
| core constraints | Directly splice original nodescannot copy the value to create a new node |
| data range | Number of nodes [0, 50]node value [-100, 100]，May be empty, may have duplicate values |
Let’s take a look at a few examples:
| enter | output |
|---|---|
l1 = [1,2,4], l2 = [1,3,4] |
[1,1,2,3,4,4] |
l1 = [], l2 = [] |
[] |
l1 = [], l2 = [0] |
[0] |
When you get questions during the interview, don’t rush to write them. First, take the initiative to confirm three points with the interviewer, and your favorability will be directly maxed out:
“Let me confirm first: ① The two linked lists themselves are in order, so they can be merged using double pointers; ② The number of nodes may be 0, and an empty linked list needs to be processed; ③ The question says ‘splicing all nodes’, which I understand asRearrange pointers in placeno new node is needed, and the space can be O(1). “
With just this sentence, the interviewer already knows that you are an engineering-minded person.
2. Solving the question: What is the essence of the question?
In actual development, we often encounter the scenario of “merging two ordered data streams” – the merge step of merging two ordered log streams, database merge query, and merge sort. The essence of this question isThe linked list version of the merge step in merge sort。
For example: you have two decks of sorted playing cards in your hand. Each time you compare the top card of the two stacks, take out the smaller one and put it into the new stack until one stack is empty and the other stack is put on top.
Before you get started, think through 3 questions:
- Both linked lists are ordered → Natural merge scene, double pointers scan from front to back, no need to reorder;
- The result is that the head node is undefined → Whether the head comes from l1 or l2 depends on the first round of comparison, and it must be covered with sentinel nodes to avoid special judgments;
- What to do after one party has left? → The remaining items on the other side are already in order.Connect the whole section at oncestop comparing one by one.
By the way, a common knowledge about data structure: Single linked list node = data field val + pointer field nextthe nodes are not consecutive in the memory, relying on next string together,You can only go backwards in one direction– This is why the position pointer must be preserved when merging.
3. Solution 1: Iteration + Sentinel Node (preferred for interviews)
core idea
use Dummy node Act as a sentinel head to avoid the trouble of emptying the head node; use cur The pointer always points to the end of the result linked list, and the double pointers traverse the two original linked lists at the same time, and the one with the smaller one takes over; finally, the entire unfinished linked list is directly put together at the end.
One sentence summary:Pick up whoever is younger, move back after picking up。
Why do you have to dummy?
Many people fail not in logic, but in “which node to return to”. Without the introduction of sentinels, the head of the resulting linked list is determined dynamically, and you have to write additional information outside the loop. if (head == null) Branch to record the head node, the code is ugly and easy to leak.
The function of the sentinel is to place aplaceholder dummy(Just like putting a dummy at the head of the queue when queuing), let the action of “connecting nodes” be unified from beginning to end. cur.next = xxx,at last return dummy.next Done.
The essence of the sentinel node: replace an entire boundary branch with a meaningless preceding node. The amount of code and the error rate are both reduced.
Merger process diagram
by l1=[1,2,4]、l2=[1,3,4] For example, the whole process looks like this:
Let’s 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) {
// ① 哨兵节点：统一头节点逻辑，彻底消灭空指针特判
ListNode dummy = new ListNode(-1);
ListNode cur = dummy; // cur 始终指向结果链表尾部
// ② 双指针共同遍历，谁小接谁
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) { // ③ 用 <=，等值取 l1，保证稳定性
cur.next = l1;
l1 = l1.next; // 被选中的链表指针后移
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next; // ④ 尾指针同步后移
}
// ⑤ 剩余段一次接完，无需再循环
cur.next = (l1 != null) ? l1 : l2;
return dummy.next; // ⑥ dummy 只是工具人，不进入结果
}
}
Four technical highlights of this code
| Highlights | illustrate | income |
|---|---|---|
| Sentinel node dummy | Unify all insertion logic with fake header | Eliminate the “first insertion” special penalty and reduce the number of branches by half |
| The remaining sections are picked up one by one | cur.next = (l1 != null) ? l1 : l2 |
Don’t worry about the ending in the loop. Don’t use the loop to do things that can be done in O(1) |
| Reuse nodes in place | Only change next pointer, no new |
Meets the “splicing” requirements of the topic, space O(1) |
<= Keep stable |
When the values are equal, l1 is preferred. | The relative order of equivalent nodes is not disordered |
Let’s focus here <=: The difference of an equal sign reflectsstable sortingconsciousness. In production scenarios such as multi-field sorting and merging log streams, stability is a hard requirement. The interviewer sees you using <= If you can tell why, your eyes will light up.
4. Solution 2: Recursive method (elegant, but at a cost)
core idea
The recursive way of thinking is “What to do at this step, leave the rest to the next layer“: Select the smaller of the two head nodes each time and make it next Point to “the merged result of the remaining two linked lists” and recurse layer by layer until one of them is empty.
Let’s take a look at the three elements:
- Termination condition：
l1 == nullreturnl2；l2 == nullreturnl1 - Current level logic: Whose head node is smaller?
nextPoints to “remaining merged result” - return: The current smaller node is used as the head of the result of this layer.
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 递归出口：任一链表为空，直接返回另一条
if (l1 == null) return l2;
if (l2 == null) return l1;
// 选小节点，递归合并剩余部分
if (l1.val <= l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
The subtlety of recursion is “trust”: I trust mergeTwoLists(剩下的部分) An ordered linked list must be returned, so I only need to decide who is currently in charge – this is the idea of divide and conquer + mathematical induction.
The expansion and backtracing process of the entire call stack:
Hidden engineering hazards of recursion: stack overflow
The time complexity is also O(m+n), and each node can be processed at most once. But the space complexity is O(m+n)——The recursion depth is equal to the length of the merged linked listeach layer of calls occupies a stack frame on the JVM stack.
Note: This is not “extra array” level space, it is call stack space. The default stack size of JVM is about 512KB~1MB. Each stack frame occupies dozens to hundreds of bytes. The length of the linked list reaches 100,000 levels. The recursive version is directly
StackOverflowError。
The number of nodes in this question is ≤ 50, and there is no actual risk in recursion. But when the production environment or the length of the linked list is uncontrollable,Iteration is the default answer in engineeringrecursion is only used to demonstrate clarity of thinking.
5. Comparison and selection of two solutions
| Dimensions | Iterative method (sentinel + tail insertion) | recursive method |
|---|---|---|
| time complexity | O(m+n) one traversal | O(m+n) Each layer processes one node |
| space complexity | O(1) merge in place ✅ | O(m+n) recursive stack overhead⚠️ |
| Code simplicity | Moderate, logical and intuitive | Minimalist, core 4 lines |
| Stack overflow risk | None✅ | Long linked lists will explode the stack💥 |
| production availability | First choice | Data size needs to be assessed |
| Interview recommendation | ⭐⭐⭐⭐⭐ Standard answer | ⭐⭐⭐ Bonus points added |
Memorize interview skills directly：
“I will write the iterative version first, which has O(1) space and no risk of stack overflow. It is the standard answer in engineering. I can also write recursion, and the code is shorter, but the stack depth is O(m+n), and the large amount of data has the risk of stack explosion, so I choose iteration for production.”
Demonstrates both breadth and engineering judgment. This kind of “hierarchical thinking” is more valuable than AC itself.
6. Technical difficulties and pitfalls (key points, screenshots recommended)
The table below is a summary of the cars I have actually turned over in interviews over the years. Each one corresponds to a specific solution:
| # | difficulty | Why is it easy to make mistakes | solution |
|---|---|---|---|
| 1 | The ownership of the head node is uncertain | Whether the result head comes from l1 or l2 depends on the first round of comparison, which requires a lot of special judgment. | Introduce the sentinel node dummy, and finally return dummy.next Unified closing |
| 2 | Empty linked list/one long and one short | direct access l1.val Throw NPE |
while The condition guarantees that the double is not empty; the remaining segments are grafted in their entirety, and are automatically compatible with all single-empty and double-empty scenarios. |
| 3 | The pointer order is written in reverse → broken link | Move first l1 Then connect the node, or take it first l1.next If you move again, you will lose the node directly. |
Fixed routine:Pick up first cur.next → Go again l1 = l1.next →Move back cur = cur.nextthe order of the three steps cannot be messed up |
| 4 | Forgot to move cur → overwrite/infinite loop | Only move cur in a certain branch. The next assignment will overwrite the previous connection and there will be only one node left in the linked list. | cur = cur.next Put it at the end of the loop, don’t put it in if/else |
| 5 | Loop condition written incorrectly | written as while (l1 != null || l2 != null)the loop body is all handled by null pointers, which is long and prone to NPE. |
Use standard writing method &&hand “a certain party has finished” to a line of splicing after the loop |
| 6 | Loss of stability of equivalent nodes | use < Causes equal elements to be out of order across linked lists |
use <=equal value is given priority to l1 |
| 7 | Habitual new node | Copy the value to the new node, the space becomes O(n) and the original linked list is destroyed. | Changing pointers in place to reuse nodes is the key to O(1) space. |
| 8 | recursive stack overflow | Recursion depth = m+n, long linked list bursts the stack | Iteration for production; indicate “can be rewritten as iteration” when recursion is required |
| 9 | Mistakenly creating a loop | Using the “head insertion method” to merge, the wrong pointer connection causes the linked list to form an endless loop. | Adhere to the tail insertion method and never new data nodes |
| 10 | k-way extension timeout | K linked lists are merged sequentially, O(k·N) timeout | Heap/divide and conquer down to O(N log k), see below |
Attach another copyInterview checklistgo over it after writing the code:
- ❌ Pour the values into the array, sort them, and then create a new linked list → the space is O(n), destroy the original structure, and do not reflect the linked list operation at all, so points will be deducted directly
- ❌
if (dummy = new ListNode(-1))→ Assignment is written as judgment, a classic clerical error - ❌ Leaking in the loop
cur = cur.next→ The result is stuck at the second node or an infinite loop - ❌ Visit if there is no empty space
l1.val→ Null pointer exception - ❌ Return
dummyinstead ofdummy.next→ The result is one more -1 out of thin air - ❌ Write while after the loop ends to move the remaining nodes one by one → superfluous
7. Two bright spots to widen the gap
If your goal is a large-scale SSP, just writing it correctly is not enough. The following two pieces of code are my most recommended “muscle flexing” postures in actual interview coaching.
Highlight 1: Comparator generalization – from “brushing algorithm” to “writing middleware”
By taking out the “comparison rules”, object linked lists and reverse merges can be reused:
public static ListNode merge(ListNode a, ListNode b, Comparator 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;
}
The interviewer’s inner OS: This person has abstract consciousness and is not someone who memorizes questions. one
ComparatorParameters, directly write an algorithm question with the flavor of middleware.
Highlight 2: k-way merging – priority queue version
This is from question 21 to question 23The only correct jump posturethe sentinel writing method is reused unchanged:
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue pq =
new PriorityQueue<>(Comparator.comparingInt(n -> n.val));
for (ListNode h : lists) if (h != null) pq.offer(h); // k 个头进堆
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); // 后继补位
}
return dummy.next;
}
time complexity O(N log k)N is the total number of nodes.
8. Interviewer’s question set (prepare in advance, points will be awarded if asked)
Q1: Why use sentinel nodes? Can you not use it?
OK, but you have to write one more if (head == null) Branch record head node. The essence of Sentinel is to replace an entire border branch with a little extra space, making the code shorter and less error-prone.
Q2: Explain clearly the space complexity of recursion.
The recursion depth is equal to m+n, each layer has one stack frame, and the space is O(m+n). The recursive version will collapse directly when the linked list has millions of nodes, so iteration is used for production.
Q3: How to merge K ordered linked lists (LeetCode 23)?
Comparison of three ideas:
| plan | Ideas | time complexity | evaluate |
|---|---|---|---|
| Merge them two by two | Repeatedly call this function | O(k·N) | Slow, timeout due to large data volume |
| small top pile | Maintain K current minimum nodes | O(N log k) | Recommended✅ |
| divide and conquer merge | Merge in half like merge sort | O(N log k) | Optimal and more memory-friendly |
Q4: What should I do after the merger?
meet l1.val == l2.val When , connect a node, move both pointers backward, and skip the repetition.
Q5: What should I do if the linked list is in descending order?
Two ways: ① reverse each and then merge, and then reverse back if necessary; ② change the comparison logic to take the larger one first, and finally reverse the whole.
Q6: What is the difference between merging two ordered arrays (LeetCode 88) and this question?
The array version should be fromback to frontFill in to avoid overwriting unprocessed elements; in the linked list version, only the pointer is changed and there is no overwriting problem, just connect from front to back. In addition, merge sorting requires O(n) auxiliary arrays to merge on the array, and changing the pointer on the linked list is completed in place, but the space is reduced to O(1).
Q7: What if the original linked list is not allowed to be modified and only new nodes can be used?
Then you can’t change the pointer in place, so new ListNode After copying the values and then splicing them, the space degrades to O(m+n).
Q8: How to write the linked list version of merge sort (LeetCode 148)?
Find the midpoint of the fast and slow pointers → disconnect → sort separately → call the merge of this question.This question is its foundation.
Q9: Is there any difference between singly linked lists and doubly linked lists in this question?
Doubly linked lists can directly insert O(1) at the tail and support reverse traversal; singly linked lists can only rely on dummy + tail to maintain the tail pointer.
9. 30-second dictation template (memorize it and use it directly)
“The essence of this question is the merge step of merge sort. I useDouble pointer + sentinel nodeDo: dummy to eliminate the special judgment of the head node, whoever is younger in the loop will pick up whoever, use
<=Ensure stability; after exiting the loop, the remaining segments are directly grafted as a whole, because the original linked list is already in order. The time is O(m+n), the extra space is O(1), and it is an in-place rearrangement. There is also a recursive writing method. The code is shorter but the stack depth is O(m+n). The large amount of data has the risk of bursting the stack, so I choose iteration in engineering. If it is expanded to k-way, I will use small top heap or divide and conquer, the complexity is O(N log k). “
After writing the code, you can also take the initiative to add a sentence of boundary analysis: “I noticed several boundary conditions: l1 is empty, l2 is empty, both are empty, one is long and one is short, and the node values are equal – the dummy + ternary operator is naturally compatible with all.” Don’t wait for the interviewer to ask, take the initiative to say it, and your favorability will be high.
Finally, the interviewer’s rating perspective is attached, so you can self-assess which level you are in:
| Rating | Performance |
|---|---|
| 🟢 Excellent | The iterative version is written correctly in one go + proactively improves stability + can push k paths |
| 🟡 Passed | I can write the merge logic, but the processing of the head node is cumbersome. |
| 🔴To be improved | Create new node splicing/forgot to return dummy.next / create a ring |
write at the end
The essence of this question is not in the code length, but in three engineering ideas:Use dummy to eliminate boundary branches, identify the essence of the “order → merge” algorithm, and make a choice between iteration and recursion based on data size.. If there are only 3 minutes left on the scene, hand in the iterative version; if there are 10 minutes, tell the evolution path of recursion and small heap.
One sentence to end:The sentinel node covers the head, and the tail pointer is pushed back, leaving a section that is connected, O(m+n) time, O(1) space.
Related topics are put here together. It is recommended to brush them in order:LeetCode 21(this question)→ LeetCode 88 合并两个有序数组 → LeetCode 23 合并K个升序链表 → LeetCode 148 排序链表add one more剑指 Offer 25this linked list merge line is complete.
Click here if you find it useful.focus onthis “Algorithm 198 Questions” series is updated every week, covering everything from linked lists and binary trees to dynamic programming and system design.
2 articles are updated every week, more algorithm questions are in:
Today’s interaction: What’s the most outrageous pitfall you’ve ever encountered on a linked list? Did it create a ring or return a dummy? Let’s chat in the comment area. I’ll write a teardown of the scam with the most likes in the next issue.
