c++中如何合并两个有序链表_c++有序链表合并算法实现

合并升序单链表常规用双指针遍历取较小节点接入新链表，时间O(m+n)、空间O(1)，需用dummy节点统一入口并正确处理剩余链表；递归写法简洁但有栈溢出风险，须首行判空；降序只需改比较符；std::list须用merge()且要求已排序。

合并两个升序单链表的常规写法

直接用双指针遍历两个链表，每次取较小节点接入新链表尾部，时间复杂度 O(m + n)，空间复杂度 O(1)（不计返回链表）。关键在于处理好头节点和边界条件。

常见错误：忘记初始化 dummy 节点、漏判某链表提前走完、误用 == 比较指针值而非节点值。

• 必须用 ListNode* dummy = new ListNode(0) 统一入口，避免空链表特判
• 循环条件是 l1 != nullptr && l2 != nullptr，不是 l1->next 或 val 判空
• 循环结束后，需手动接上非空剩余链表：cur->next = l1 ? l1 : l2

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;
}

递归实现要注意栈深度和空指针访问

递归写法简洁但隐含风险：当链表长度超千级时可能触发栈溢出；且必须在首行检查 nullptr，否则 l1->val 会崩溃。

适用场景：教学演示、链表极短、或明确限制了最大长度（如 LeetCode 默认安全）。

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

• 递归终止条件只能是 l1 == nullptr 或 l2 == nullptr，不能只写一个
• 递归调用前必须确保 l1 和 l2 都非空，否则 l1->next 可能非法
• 返回的是“当前最小节点”，不是新分配节点，所以无需 new

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

合并降序链表只需改比较符号

算法结构完全一致，唯一区别是把 改成 >=。但要注意：如果输入链表方向不一致（一个升序一个降序），不能直接套用，必须先统一方向或改逻辑。

容易被忽略的点：有些题目要求“稳定合并”，即相同值时优先保留第一个链表的节点——此时需用 而非 ，否则会破坏稳定性。

• 升序合并用 l1->val val
• 降序合并用 l1->val >= l2->val
• 若要求稳定，一律用 或 >=，禁用 / >

使用 std::list 时不能直接复用指针逻辑

std::list 是双向链表容器，不暴露内部节点指针，也不允许你手动拼接 next 字段。想合并两个 std::list，得用成员函数 merge()，且要求两者都已排序。

错误做法：试图取 ::begin() 去做指针操作；或自行遍历插入——这会退化为 O(n²)。

• 调用前必须确保两个 std::list 都已按同一规则排序（如都升序）
• list1.merge(list2) 后，list2 变为空，所有节点移入 list1
• 若原始数据无序，先用 sort()，再 merge()

std::list a = {1, 3, 5};
std::list b = {2, 4, 6};
a.merge(b); // a 变为 {1,2,3,4,5,6}，b 为空

实际写的时候，最常卡住的地方不是逻辑，而是空指针解引用和头节点管理——哪怕看懂了算法，少写一行 cur = cur->next 或错判一次 l1 是否为空，结果就全乱。