C++怎么合并两个有序链表_C++数据结构教程【高频】

mergetwolists需用哑节点+双指针，循环比较取小值并后移，循环后用cur->next = l1 ? l1 : l2接剩余链表，避免空指针解引用和节点遗漏。

mergeTwoLists 函数怎么写才不漏节点

直接用双指针遍历两个链表，谁小取谁，取完就往后挪；但最容易漏的是「其中一个链表走完后，另一个没接全」。很多人只在循环里处理比较逻辑，忘了循环外要手动拼上剩余部分。

常见错误现象：nullptr 访问、结果链表结尾断开、最后一个节点丢失

• 必须初始化一个哑节点（dummy），避免空链表特判和头节点操作混乱
• 循环条件用 l1 != nullptr && l2 != nullptr，别用 while (l1 || l2)——容易在某一方为 nullptr 时继续解引用
• 循环结束后，用 cur->next = l1 ? l1 : l2 接上剩余段，别再写一遍 if-else 判断

示例关键片段：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {     ListNode dummy(0);     ListNode* cur = &dummy;     while (l1 && l2) {         if (l1->val <= l2->val) {             cur->next = l1;             l1 = l1->next;         } else {             cur->next = l2;             l2 = l2->next;         }         cur = cur->next;     }     cur->next = l1 ? l1 : l2;     return dummy.next; }

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

递归版简洁，但实际工程中基本不用——它把链表长度直接转成调用栈深度。哪怕只是 10⁵ 级别的有序链表，在默认栈空间下大概率触发 stack overflow。

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

使用场景：仅限教学演示或极短链表（

• 每次递归调用都压入函数帧，含参数、返回地址、局部变量，开销远大于迭代的几个指针变量
• MSVC 默认栈大小约 1MB，GCC/Linux 默认 8MB，但链表节点数超 10⁴ 就已危险
• 无法提前终止：即使发现某链表已空，仍需等所有递归返回才能回溯，没法像迭代那样直接跳转

合并过程要不要 new 新节点

不需要，也不应该。原地复用原有节点即可——既省内存，又避免深拷贝带来的值语义歧义（比如节点里有指针成员）。

性能影响明显：每 new 一次就是一次堆分配，O(n) 次分配 + 可能的内存碎片；而复用只是改指针指向，纯 O(1) 操作

• 只要不修改节点的 val 字段，只调整 next 指针，就完全安全
• 如果题目明确要求「不能修改原链表」，才考虑深拷贝，但这时应由题干说明，c++ 默认按原地合并理解
• 注意：返回的是新链表头，但内部节点仍是原链表中的对象，生命周期由调用方保证

LeetCode 提交时报错 member access within null pointer

这是最常卡住人的运行时错误，根本原因是用了 l1->val 或 l1->next 却没先检查 l1 是否为空。

典型发生位置：循环体内、三元表达式右侧、return 前的最后一步

• 错误写法：if (l1->val val) —— 必须先写 if (l1 && l2) 再比值
• 安全写法：所有对 -> 的访问前，确保指针非空；宁可多写一行 if (!l1) return l2; 作守卫
• 调试技巧：本地跑时加断言，比如 assert(l1); assert(l2);，快速暴露空指针路径

事情说清了就结束：合并本身不难，难的是边界全想到、空指针全防住、内存不乱 new。