C++实现LeetCode(21.混合插入有序链表)

前言

先纠正题面：LeetCode 第 21 题的英文名是 Merge Two Sorted Lists，标准译法是「合并两个有序链表」，「混合插入」是误译。题目给定两个升序单链表的头节点，要求把它们合并成一个新的升序链表，并返回头节点；新链表由原来的节点拼接而成，不需要新建节点。

这个误译容易带来一个错误方向：有人以为要把一个链表的节点「插入」到另一个链表的指定位置，于是去写查找插入点的逻辑。实际做法简单得多——两个指针各扫一条链表，每次取较小的节点接到结果尾部，直到一条走空，再把另一条剩余部分整体接上。

链表的题不难在算法，难在指针操作：哑节点怎么用、尾指针何时前进、最后剩的那段怎么接、返回的到底是不是栈上对象。本文给出迭代与递归两种写法，逐行说明指针变化，并讨论真实工程里的所有权问题。

一、迭代解法：哑节点与尾指针

合并的核心是维护一个结果链表的尾部。如果结果为空，第一次插入要修改头指针；如果结果非空，只需修改尾节点的next。为了消除「空链表」这个特殊分支，引入一个哑节点（dummy node）：它不存储有效数据，只作为占位，最终返回dummy.next。

算法步骤：

1. 
   
2. 创建栈上的哑节点dummy，令tail = &dummy。
3. 
   
4. 当l1和l2都非空时，比较l1->val与l2->val，把较小者接到tail->next，然后让对应指针后移。
5. 
   
6. 每次接完，tail后移到新节点。
7. 
   
8. 循环结束时，至少一条链表为空，把另一条未走完的部分整体接到tail->next。
9. 
   
10. 返回dummy.next。
11. 
    

第 4 步是很多人漏掉的地方。循环条件要求两条都非空，因此退出时一定有一条还剩节点；这些节点本身已经有序，且都大于等于已合并部分的最后一个值，所以不需要逐个再比较，直接接上即可。漏掉这一步，结果会丢掉尾部。

第 5 步返回的是dummy.next，不是&dummy。哑节点是栈上的局部对象，函数返回后即销毁，返回它的地址是悬垂指针；即使不崩溃，调用方拿到的也是一个没有数据意义的节点。

// 适用于 C++17
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode dummy; // 栈上占位，不参与返回
ListNode* tail = &dummy;

while (l1 != nullptr && l2 != nullptr) {
if (l1->val <= l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}

tail->next = (l1 != nullptr) ? l1 : l2;
return dummy.next;
}

时间复杂度 O(m + n)，其中 m、n 分别是两条链表的长度；空间复杂度 O(1)，只用了两个指针和一个哑节点。这里没有新建节点，结果链表复用了输入节点。

比较符用<=还是<不影响升序的正确性，但影响相等元素的先后：用<=时，l1的节点排在l2的等值节点之前，相当于对「相等时保持 l1 优先」这一顺序是稳定的。若题目对相等元素的相对次序有要求，需要明确选择。

二、递归解法：把问题缩小到子链表

递归的思路是：如果l1为空，返回l2；如果l2为空，返回l1；否则比较两个头节点，较小者的next指向「其余部分合并后的结果」，返回这个较小者。

// 适用于 C++17
ListNode* mergeTwoListsRecursive(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) return l2;
if (l2 == nullptr) return l1;

if (l1->val <= l2->val) {
l1->next = mergeTwoListsRecursive(l1->next, l2);
return l1;
}
l2->next = mergeTwoListsRecursive(l1, l2->next);
return l2;
}

递归的每一层只做一次比较和一次指针赋值，正确性依赖于「子问题仍然是合并两条有序链表」这一不变量。时间复杂度同样是 O(m + n)，但空间复杂度是 O(m + n)，因为每层调用都占栈帧。链表很长时（例如十万个节点），递归可能耗尽栈空间，工程代码应优先用迭代版。

递归版还有一个容易忽略的细节：l1->next = mergeTwoListsRecursive(l1->next, l2);必须在递归返回后赋值，不能写成先保存再修改。递归过程中会修改子链表的next，但不会修改l1本身的val，所以比较依据始终有效。

三、所有权、复用与工程写法

LeetCode 的判题环境不要求释放节点，函数返回后由判题器统一回收。但在真实工程里，节点由谁拥有、谁负责释放，必须提前约定。

上面的迭代写法把输入链表的节点「搬」到了结果链表里，函数返回后，原来的两个头指针仍然指向这些节点的一部分。如果调用方随后又用旧头指针去释放整条链表，就会与结果链表重复释放，属于严重的资源管理错误。正确做法是：合并后只保留结果链表的头，旧头指针不再使用；或者在合并前明确「输入所有权转移给函数」。

用现代 C++ 表达所有权时，可以用std::unique_ptr<ListNode>串联节点，合并时用std::move转移next。这样不需要手写delete，异常路径也能正确释放。不过 LeetCode 的接口签名是裸指针，刷题时不必强行改写；理解「节点被复用、旧头失效」这一点，比背智能指针写法更重要。

另一个边界是空输入。两条都为空时，循环不执行，tail->next被赋为nullptr，返回nullptr，正确。一条为空时，循环不执行，直接接上另一条，也正确。只有一条链表本身含环或未按升序排列时，算法才会失效——题目保证有序且无环，这两个前提不能省。

常见坑点

1. 返回哑节点的地址

❌return &dummy;

✅return dummy.next;，哑节点只是栈上占位。

2. 忘记拼接剩余链表

❌ 循环结束后直接return dummy.next;，丢掉未走完的那一段。

✅tail->next = (l1 != nullptr) ? l1 : l2;再返回。

3. 尾指针忘记前进

❌ 接完节点后不写tail = tail->next;，下一次覆盖同一个next。

✅ 每次拼接后移动tail，保持它始终指向结果尾部。

4. 先移动指针再拼接

❌l1 = l1->next; tail->next = l1;，接上的是下一个节点，当前节点丢失。

✅ 先把l1接到tail->next，再l1 = l1->next。

5. 递归深度过大

❌ 对十万级节点的链表使用递归版。

✅ 长链表用迭代版；递归只适合节点数可控或作为教学示例。

6. 合并后继续使用旧头指针

❌ 合并完成后又用原来的l1、l2遍历或释放。

✅ 合并后只使用返回的新头；输入头指针视为失效。

7. 认为必须新建节点

❌ 为每个元素new ListNode，再复制值。

✅ 直接复用原节点，只改next；这样空间 O(1)。

8. 把题目理解成「插入到指定位置」

❌ 按「混合插入」的字面意思去查找插入点。

✅ 第 21 题就是两条有序链表的归并，双指针扫描即可。

总结

合并有序链表的本质是一次归并排序的「归并」步骤：两个指针各走一遍，谁小接谁，走完为止，剩下的整体挂上。把哑节点、尾指针、剩余段这三处写对，再想清楚节点复用带来的所有权变化，这道题就不会在边界上翻车。