给定两个按非递减顺序排列的单链表 A 和 B，将它们合并成一个新的单链表 C，使 C 也按非递减顺序排列。合并过程应复用已有节点，不额外申请大量新节点。

题目

合并两个有序单链表

将两个有序单链表合并为一个有序单链表。

任务要求

1. 从标准输入读入两个链表的长度与元素值；
2. 通过调整 next 指针完成合并，不允许先把元素全部读入数组再排序输出；
3. 输出合并后的链表节点值序列。

输入格式

• 第一行：一个整数 n，表示链表 A 的长度；
• 第二行：n 个整数，按从头到尾顺序给出链表 A 的节点值（已排序）；
• 第三行：一个整数 m，表示链表 B 的长度；
• 第四行：m 个整数，按从头到尾顺序给出链表 B 的节点值（已排序）。

输出格式

• 一行 n + m 个整数，为合并后的有序链表节点值序列；
• 相邻整数之间用单个空格分隔，行末不要有多余空格。

数据范围与限制

项目	范围
链表 A 长度 n	0 ≤ n ≤ 10⁵
链表 B 长度 m	0 ≤ m ≤ 10⁵
节点值	−10⁹ ≤ 值 ≤ 10⁹
时间复杂度要求	O(n + m)
额外空间限制	O(1)，仅允许常数级指针变量

样例

样例输入 1

3
1 3 5
3
2 4 6

样例输出 1

1 2 3 4 5 6

样例输入 2

0

3
1 2 3

样例输出 2

1 2 3

样例输入 3

2
1 1
2
1 1

样例输出 3

1 1 1 1

样例解释

以样例 1 为例，链表 A：1 → 3 → 5，链表 B：2 → 4 → 6：

步骤	结果链表尾部	A 当前头	B 当前头	接上的节点	原因
初始	dummy	1	2	—	—
1	1	3	2	1（来自 A）	1 <= 2
2	2	3	4	2（来自 B）	2 < 3
3	3	5	4	3（来自 A）	3 < 4
4	4	5	6	4（来自 B）	4 < 5
5	5	null	6	5（来自 A）	A 还有节点
6	6	null	null	6（来自 B）	接上 B 剩余

最终链表：1 → 2 → 3 → 4 → 5 → 6。

如何验证

先安装 Node.js、pnpm 和支持 C++17 的编译器。GNU Make 是首选入口，但不是强制依赖。

# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make score

Windows 没有安装 Make 时，在仓库根目录使用完全相同的评分内核：

pnpm lab:doctor -- labs/chapter-01/exercise/E-01-06-singly-linked-list-merge
pnpm lab:run -- labs/chapter-01/exercise/E-01-06-singly-linked-list-merge
pnpm lab:run -- labs/chapter-01/exercise/E-01-06-singly-linked-list-merge --case 001-sample
pnpm lab:score -- labs/chapter-01/exercise/E-01-06-singly-linked-list-merge

make run 在答案尚未全对时仍正常返回，避免 Make 把学习结果显示成工具故障；make score 是严格入口，只有 100 分才返回成功。标准输出参与判题，调试信息请写入标准错误。

• 样例输入与输出完全一致
• 四组边界自测通过
• 程序满足 O(n + m) 且未使用排序
• 能解释为什么哑节点能避免合并空链表时的分支判断

思考题

1. 与 Lab 01-03 的有序顺序表合并相比，链表合并的"一趟完成"在代码结构上有何不同？
2. 如果要求合并后的链表严格递增（不含重复），需要在合并逻辑中增加哪些处理？

题解

点击查看题解

思路

类似归并排序的合并过程，使用哑节点作结果链表的临时头，逐次取两链表中较小者接到结果尾部。

算法步骤

1. 创建哑节点 dummy，tail = dummy；
2. 当 A 和 B 都非空：
   • 若 A->val <= B->val，tail->next = A，A = A->next；
   • 否则 tail->next = B，B = B->next；
   • tail = tail->next；
3. 将非空链表剩余部分直接接上；
4. 返回 dummy->next。

复杂度分析

• 时间复杂度：O(n + m)，每个节点只访问一次。
• 空间复杂度：O(1)，仅使用常数个指针，复用原有节点。

边界注意

• 其中一个链表为空：直接返回另一个；
• 两个都为空：返回空链表。

点击查看参考代码

#include <cstddef>
#include <iostream>
#include <vector>

struct Node {
    long long value{};
    Node* next = nullptr;
};

Node* build_list(std::size_t n) {
    Node* head = nullptr;
    Node* tail = nullptr;
    for (std::size_t i = 0; i < n; ++i) {
        long long v = 0;
        std::cin >> v;
        Node* node = new Node{v, nullptr};
        if (!head) head = tail = node;
        else { tail->next = node; tail = node; }
    }
    return head;
}

void print_list(Node* head) {
    bool first = true;
    for (Node* p = head; p; p = p->next) {
        if (!first) std::cout << ' ';
        std::cout << p->value;
        first = false;
    }
    std::cout << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::size_t n = 0, m = 0;
    std::cin >> n;
    Node* a = build_list(n);
    std::cin >> m;
    Node* b = build_list(m);

    Node dummy{0, nullptr};
    Node* tail = &dummy;

    while (a && b) {
        if (a->value <= b->value) {
            tail->next = a; a = a->next;
        } else {
            tail->next = b; b = b->next;
        }
        tail = tail->next;
    }
    tail->next = a ? a : b;

    print_list(dummy.next);
}