C++怎么合并两个排序的链表

# C++怎么合并两个排序的链表

## 引言

在数据结构与算法中，合并两个已排序的链表是一个经典问题。该问题不仅考察对链表操作的理解，还涉及递归和迭代两种解题思路。本文将详细介绍在C++中如何高效实现这一操作，包括代码实现、复杂度分析以及相关应用场景。

---

## 问题描述

给定两个**非递减顺序排列**的链表`list1`和`list2`，要求将它们合并为一个新的**升序链表**并返回。新链表应通过拼接原链表的节点组成。

**示例输入：**
```cpp
List1: 1 -> 3 -> 5
List2: 2 -> 4 -> 6

示例输出：

1 -> 2 -> 3 -> 4 -> 5 -> 6

---

链表节点定义

首先，我们需要定义链表节点的结构。在C++中，通常如下表示：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

---

方法一：迭代法

算法思路

1. 创建一个虚拟头节点（dummy node）作为新链表的起始点。
2. 使用指针curr跟踪新链表的当前节点。
3. 比较两个链表的当前节点值，将较小者接入新链表。
4. 移动被选中链表的指针到下一个节点。
5. 重复步骤3-4直到某一链表遍历完毕。
6. 将剩余非空链表直接接入新链表末尾。

代码实现

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode dummy(0); // 虚拟头节点
    ListNode* curr = &dummy;
    
    while (list1 && list2) {
        if (list1->val <= list2->val) {
            curr->next = list1;
            list1 = list1->next;
        } else {
            curr->next = list2;
            list2 = list2->next;
        }
        curr = curr->next;
    }
    
    // 处理剩余节点
    curr->next = list1 ? list1 : list2;
    return dummy.next;
}

复杂度分析

• 时间复杂度：O(n + m)，其中n和m分别为两个链表的长度。
• 空间复杂度：O(1)，仅使用常数级别的额外空间。

---

方法二：递归法

算法思路

1. 递归基：如果任一链表为空，直接返回另一链表。
2. 比较两个链表头节点的值：
   • 若list1->val较小，则将list1->next与list2合并的结果接入list1。
   • 反之同理。
3. 返回当前较小节点作为新链表的头节点。

代码实现

ListNode* mergeTwoListsRecursive(ListNode* list1, ListNode* list2) {
    if (!list1) return list2;
    if (!list2) return list1;
    
    if (list1->val <= list2->val) {
        list1->next = mergeTwoListsRecursive(list1->next, list2);
        return list1;
    } else {
        list2->next = mergeTwoListsRecursive(list1, list2->next);
        return list2;
    }
}

复杂度分析

• 时间复杂度：O(n + m)，每次递归调用处理一个节点。
• 空间复杂度：O(n + m)，递归栈的深度最多为n+m。

---

方法对比

方法	优点	缺点
迭代法	空间效率高（O(1)）	代码稍显冗长
递归法	代码简洁，逻辑清晰	栈空间开销大（O(n+m)）

---

边界条件处理

实际编码时需考虑以下特殊情况： 1. 一个链表为空：直接返回另一个链表。 2. 两个链表均为空：返回nullptr。 3. 链表有重复值：题目要求非递减顺序，重复值需保留。

---

应用场景

1. 归并排序：合并链表是归并排序的核心步骤。
2. 多路归并：如合并K个有序链表的基础操作。
3. 数据库系统：合并多个有序结果集。

---

完整测试用例

#include <iostream>
using namespace std;

// 打印链表
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "nullptr" << endl;
}

// 测试代码
int main() {
    // 构造链表1: 1->3->5
    ListNode a(1), b(3), c(5);
    a.next = &b; b.next = &c;
    
    // 构造链表2: 2->4->6
    ListNode d(2), e(4), f(6);
    d.next = &e; e.next = &f;
    
    cout << "List1: "; printList(&a);
    cout << "List2: "; printList(&d);
    
    // 合并链表
    ListNode* merged = mergeTwoLists(&a, &d);
    cout << "Merged: "; printList(merged);
    
    return 0;
}

输出结果：

List1: 1 -> 3 -> 5 -> nullptr
List2: 2 -> 4 -> 6 -> nullptr
Merged: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> nullptr

---

常见问题解答

Q1: 能否原地修改链表而不创建新节点？

A1: 可以。迭代法通过指针重定向实现原地合并，无需额外节点（虚拟头节点除外）。

Q2: 如何处理降序链表？

A2: 若链表为降序，可先反转链表再合并，或修改比较逻辑为list1->val >= list2->val。

Q3: 递归法的栈溢出风险？

A3: 当链表极长时（如数万节点），递归可能导致栈溢出，此时应使用迭代法。

---

扩展思考

1. 合并K个有序链表：可通过分治策略，两两合并直至剩一个链表。
2. 双向链表的合并：需额外处理prev指针，但核心逻辑相似。
3. 并行化优化：对于超大链表，可采用多线程分段合并。

---

总结

本文详细讲解了在C++中合并两个有序链表的两种方法： - 迭代法：推荐生产环境使用，空间效率高。 - 递归法：适合面试或小规模数据，代码简洁。

理解这一问题的解决方案，将为处理更复杂的链表操作（如环形链表检测、重排序等）奠定坚实基础。

---

参考文献

1. 《算法导论》 - Thomas H. Cormen
2. LeetCode官方题解 - Merge Two Sorted Lists
3. C++标准库文档 - <list>实现原理

”`

注：实际字数约1800字，可根据需要增减示例或优化细节以达到精确字数要求。