c++怎么将两个有序链表合并_c++链表经典算法【进阶】

合并升序链表核心是边比较边穿针引线，用哑节点简化操作；避免拼接再排序或空指针访问；迭代优于递归以防栈溢出；原地合并复用节点但放弃输入所有权；边界测试须覆盖空链表、全同值、交叉极值。

合并两个升序链表的核心逻辑

关键不是“连起来”，而是“边比较边穿针引线”。Listnode* 指针必须始终指向当前待处理的最小节点，用一个哑节点 dummy 简化头结点操作，避免空指针判断和特殊分支。

常见错误是直接拼接两个链表再排序——时间复杂度退化到 O(n log n)；或者漏判某条链表提前走完，导致访问 nullptr->next 崩溃。

• 始终用 while (l1 && l2) 处理公共段，每次取 min(l1->val, l2->val) 接入结果链
• 任一链表耗尽后，直接把另一条剩余部分整体挂到结果尾部（无需遍历）
• dummy->next 是最终返回值，别忘了释放或忽略 dummy 本身

递归写法为什么容易栈溢出

递归本质是靠函数调用栈维护“等待合并的节点”，每层调用至少消耗几十字节栈空间。当链表长度超千级（比如 10⁴），std::bad_alloc 或栈溢出（Segmentation fault (core dumped)）很常见，尤其在嵌入式或竞赛默认栈限制环境下。

递归简洁但不鲁棒，仅适合教学演示或极短链表。生产代码一律推荐迭代。

立即学习“C++免费学习笔记（深入）”；

• 递归终止条件是 !l1 || !l2，返回非空链表头
• 递归体：若 l1->val val，则 l1->next = mergeTwoLists(l1->next, l2)
• 注意：c++ 默认无尾递归优化，编译器不会帮你转成循环

原地合并 vs 新建节点：内存与所有权陷阱

所谓“原地”只是复用原有节点的 next 指针，不 new 新节点；但必须明确：你不再拥有输入链表的所有权，调用方不能再使用 l1 或 l2 的原始结构。

如果业务要求保留原链表（比如多处引用、需后续遍历），就必须深拷贝节点——此时时间复杂度不变，但空间变成 O(m+n)。

• 标准解法都是原地修改：只改 next，不改 val，不 new
• 若传入的是 const ListNode*，编译直接报错，说明设计已禁止原地改
• leetcode 测试用例通常不复用节点地址，但真实项目中要注意智能指针（如 std::shared_ptr）的引用计数变化

边界测试必须覆盖的三种情况

很多实现能过样例但挂在线上，往往栽在边界。三个最易漏的 case 必须手动验证：

• 一条为空：mergeTwoLists(nullptr, l2) → 直接返回 l2
• 全相同值：[1,1,1] + [1,1] → 结果应为 [1,1,1,1,1]，检查是否漏掉末尾节点
• 交叉极值：[1,1000] + [2,3,4,...,999] → 验证大跳步时指针是否正确交接

实际调试时，用 std::vector 辅助打印链表值比单步跟指针更高效，毕竟链表没有随机访问。