给定两个用静态链表表示的有序序列，将它们合并成一个新的有序静态链表。两个输入链表都按升序排列，合并后的链表也必须按升序排列。
题目
静态链表合并两个有序表
读入两个静态链表的节点信息，通过修改游标完成合并，输出合并后的节点值序列。
任务要求
- 从标准输入读入两个静态链表的节点池信息和头节点游标；
- 通过修改
next游标完成合并，不新建额外节点； - 输出合并后的有序节点值序列。
输入格式
- 第一行：一个整数
n，表示第一个链表的节点数； - 接下来
n行，每行两个整数data和next：data：节点值；next：下一个节点的下标，-1表示末尾；
- 下一行：一个整数
head_a，表示第一个链表的头节点下标； - 下一行：一个整数
m，表示第二个链表的节点数； - 接下来
m行，每行两个整数data和next； - 最后一行：一个整数
head_b，表示第二个链表的头节点下标。
输出格式
- 一行
n + m个整数，为合并后的升序节点值序列； - 相邻整数之间用单个空格分隔，行末不要有多余空格。
数据范围与限制
| 项目 | 范围 |
|---|---|
链表 A 长度 n | 0 ≤ n ≤ 500 |
链表 B 长度 m | 0 ≤ m ≤ 500 |
| 节点值 | −10⁹ ≤ 值 ≤ 10⁹ |
| 时间复杂度要求 | O(n + m) |
| 额外空间限制 | O(1)，仅允许常数级辅助变量 |
样例
样例输入 1
input
3
1 1
3 2
5 -1
0
3
2 1
4 2
6 -1
0样例输出 1
output
1 2 3 4 5 6样例输入 2
input
0
-1
2
1 1
2 -1
0样例输出 2
output
1 2样例解释
以样例 1 为例，链表 A：1 → 3 → 5（head_a=0），链表 B：2 → 4 → 6（head_b=0，在另一数组中）：
| 步骤 | pa 指向 | pb 指向 | slots[pa].data | slots[pb].data | 较小者 | tail->next 更新 |
|---|---|---|---|---|---|---|
| 初始 | 0 | 0 | 1 | 2 | — | dummy |
| 1 | 0 | 0 | 1 | 2 | A | tail->next = 0（A 的节点 1） |
| 2 | 1 | 0 | 3 | 2 | B | tail->next = 0（B 的节点 2） |
| 3 | 1 | 1 | 3 | 4 | A | tail->next = 1（A 的节点 3） |
| 4 | 2 | 1 | 5 | 4 | B | tail->next = 1（B 的节点 4） |
| 5 | 2 | 2 | 5 | 6 | A | tail->next = 2（A 的节点 5） |
| 6 | -1 | 2 | — | 6 | B | tail->next = 2（B 的节点 6） |
从 dummy->next 开始遍历，输出 1 2 3 4 5 6。
如何验证
先安装 Node.js、pnpm 和支持 C++17 的编译器。GNU Make 是首选入口，但不是强制依赖。
powershell
# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make scoreWindows 没有安装 Make 时，在仓库根目录使用完全相同的评分内核：
powershell
pnpm lab:doctor -- labs/chapter-01/exercise/E-01-15-static-linked-list-merge
pnpm lab:run -- labs/chapter-01/exercise/E-01-15-static-linked-list-merge
pnpm lab:run -- labs/chapter-01/exercise/E-01-15-static-linked-list-merge --case 001-sample
pnpm lab:score -- labs/chapter-01/exercise/E-01-15-static-linked-list-mergemake run 在答案尚未全对时仍正常返回，避免 Make 把学习结果显示成工具故障；make score 是严格入口，只有 100 分才返回成功。标准输出参与判题，调试信息请写入标准错误。
思考题
- 如果两个链表的节点存储在同一个数组池中，合并时是否需要注意游标冲突？如果分别存储在不同数组中呢？
- 静态链表合并后，未被使用的节点槽位应如何处理？工程中常见的做法是什么？
题解
点击查看题解
思路
与动态链表合并逻辑相同，使用游标代替指针，逐次取两链表当前头的较小者接到结果尾部。
算法步骤
- 创建虚拟头游标
dummy = -1，tail = dummy； pa = head_a，pb = head_b；- 当
pa != -1且pb != -1：- 若
slots[pa].data <= slots[pb].data，slots[tail].next = pa，pa = slots[pa].next； - 否则
slots[tail].next = pb，pb = slots[pb].next； tail = slots[tail].next；
- 若
- 将剩余非空链表接上；
- 从
slots[dummy].next开始遍历输出。
复杂度分析
- 时间复杂度：
O(n + m)，每个节点只访问一次。 - 空间复杂度：
O(1)，仅使用常数个游标，复用原有节点。
边界注意
- 其中一个链表为空：直接输出另一个；
- 两个输入链表使用同一数组池时，注意游标不冲突。
点击查看参考代码
cpp
#include <cstddef>
#include <iostream>
#include <vector>
struct Slot {
long long data{};
int next = -1;
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::size_t n = 0;
std::cin >> n;
std::vector<Slot> sa(n);
for (std::size_t i = 0; i < n; ++i) {
std::cin >> sa[i].data >> sa[i].next;
}
int head_a = -1;
std::cin >> head_a;
std::size_t m = 0;
std::cin >> m;
std::vector<Slot> sb(m);
for (std::size_t i = 0; i < m; ++i) {
std::cin >> sb[i].data >> sb[i].next;
}
int head_b = -1;
std::cin >> head_b;
std::vector<Slot> slots(n + m);
for (std::size_t i = 0; i < n; ++i) {
slots[i] = sa[i];
}
for (std::size_t i = 0; i < m; ++i) {
slots[n + i].data = sb[i].data;
slots[n + i].next = (sb[i].next == -1) ? -1 : static_cast<int>(sb[i].next + n);
}
if (head_b != -1) {
head_b += static_cast<int>(n);
}
int merged_head = -1;
int tail = -1;
int pa = head_a;
int pb = head_b;
while (pa != -1 && pb != -1) {
int next_node = -1;
if (slots[pa].data <= slots[pb].data) {
next_node = pa;
pa = slots[pa].next;
} else {
next_node = pb;
pb = slots[pb].next;
}
if (tail == -1) {
merged_head = next_node;
} else {
slots[tail].next = next_node;
}
tail = next_node;
}
int remain = (pa != -1) ? pa : pb;
if (tail == -1) {
merged_head = remain;
} else {
slots[tail].next = remain;
}
bool first = true;
for (int p = merged_head; p != -1; p = slots[p].next) {
if (!first) std::cout << ' ';
std::cout << slots[p].data;
first = false;
}
std::cout << '\n';
}