C++如何合并两个已排序的链表-C++-PHP中文网

合并两个已排序链表的核心逻辑是双指针遍历，每次取较小节点追加到新链表末尾；需用哨兵节点简化边界处理，遍历结束后将剩余非空链表整体接入，复用原节点、只调换next指针，时间复杂度o(m+n)，空间复杂度o(1)。

c++如何合并两个已排序的链表

合并两个已排序链表的核心逻辑是什么

关键在于用双指针遍历两个链表，每次取较小节点追加到新链表末尾。不需要额外空间存储全部节点，也不需要先拼接再排序——那样就浪费了“已排序”这个前提。

常见错误是手动管理 next 指针时漏掉边界判断，比如某链表走完后忘记把另一链表剩余部分直接接上；或者新建节点时反复调用 new，导致内存泄漏或性能下降。

推荐复用原链表节点，只调整 next 指针，不 new 新节点（除非题目强制要求深拷贝）。

用递归写法要注意什么

递归简洁，但容易栈溢出——尤其当链表长度超千级时。C++ 默认栈空间有限，std::stack 或迭代才是更稳妥的选择。

递归终止条件必须明确：任一链表为空时，直接返回另一个链表头指针。

示例逻辑：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1->val val) {
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

注意：l1->val val 中的 保证相等时优先取 <code>l1 节点，避免逻辑跳变。

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

迭代写法怎么避免空指针崩溃

核心是引入一个哑节点（dummy node），统一处理头节点插入逻辑，避免对 head 特殊判空。

容易踩的坑：

忘记在循环结束后连接非空剩余链表（if (l1) curr->next = l1; 这类语句不能省）
移动指针时写成 l1 = l1->next; 却没同步更新 curr，导致链断裂
用 curr->next = l1; 后没立刻 curr = curr->next;，下一轮赋值会覆盖前一个节点

标准流程：

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