为了方便你创建 OJ（Online Judge）测试数据，我编写了一个完整的数据生成器。该程序会自动生成 10 组测试输入（1.in ~ 10.in）并调用标准答案逻辑生成对应的输出（1.out ~ 10.out）。

数据生成器设计思路

1. 覆盖范围：涵盖了空链表、单节点、全负数、全正数、交替序列、完全重复序列、长短不一等 10 种典型情况。
2. 数据格式：严格遵循 n val1 val2... 的格式。
3. 安全性：使用 std::mt19937 随机数引擎，避免 rand() 的局限性；采用迭代法合并，确保生成 .out 时不会爆栈。
4. 性能：由于 $N, M \le 50$，生成速度极快，文件大小远小于 2MB。

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <random>
#include <string>

using namespace std;

// === 标准答案逻辑 (用于生成 .out 文件) ===
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 迭代合并函数 (最优复杂度 O(N+M))
vector<int> solve(vector<int>& a, vector<int>& b) {
    vector<int> res;
    size_t i = 0, j = 0;
    while (i < a.size() && j < b.size()) {
        if (a[i] <= b[j]) res.push_back(a[i++]);
        else res.push_back(b[j++]);
    }
    while (i < a.size()) res.push_back(a[i++]);
    while (j < b.size()) res.push_back(b[j++]);
    return res;
}

// === 数据生成逻辑 ===
void write_file(int test_id, vector<int>& a, vector<int>& b) {
    string in_name = to_string(test_id) + ".in";
    string out_name = to_string(test_id) + ".out";

    // 生成 .in 文件
    ofstream fin(in_name);
    fin << a.size();
    for (int x : a) fin << " " << x;
    fin << "\n" << b.size();
    for (int x : b) fin << " " << x;
    fin << endl;
    fin.close();

    // 生成 .out 文件
    ofstream fout(out_name);
    vector<int> res = solve(a, b);
    for (size_t i = 0; i < res.size(); ++i) {
        fout << res[i] << (i == res.size() - 1 ? "" : " ");
    }
    // 如果结果为空，按照题目要求可能输出空行
    if (!res.empty()) fout << endl; 
    fout.close();
}

int main() {
    mt19937 rng(1337); // 固定种子保证数据可重复

    for (int i = 1; i <= 10; ++i) {
        vector<int> a, b;
        int n = 0, m = 0;

        switch (i) {
            case 1: // 边界：全为空
                n = 0; m = 0;
                break;
            case 2: // 边界：L1 为空
                n = 0; m = 10;
                for(int j=0; j<m; ++j) b.push_back(j);
                break;
            case 3: // 边界：L2 为空
                n = 10; m = 0;
                for(int j=0; j<n; ++j) a.push_back(j);
                break;
            case 4: // 边界：各只有一个元素
                n = 1; m = 1;
                a.push_back(5); b.push_back(5);
                break;
            case 5: // 典型：全负数
                n = 20; m = 20;
                for(int j=0; j<n; ++j) {
                    a.push_back((int)(rng() % 50) - 100);
                    b.push_back((int)(rng() % 50) - 100);
                }
                break;
            case 6: // 典型：L1 全小于 L2
                n = 30; m = 30;
                for(int j=0; j<n; ++j) a.push_back(j - 50);
                for(int j=0; j<m; ++j) b.push_back(j + 50);
                break;
            case 7: // 典型：完全重复的序列
                n = 50; m = 50;
                for(int j=0; j<n; ++j) a.push_back(0);
                for(int j=0; j<m; ++j) b.push_back(0);
                break;
            case 8: // 典型：奇偶交替（完美插空）
                n = 40; m = 40;
                for(int j=0; j<n; ++j) a.push_back(j * 2);
                for(int j=0; j<m; ++j) b.push_back(j * 2 + 1);
                break;
            case 9: // 综合：最大随机范围（含重复）
                n = 50; m = 50;
                for(int j=0; j<n; ++j) a.push_back((int)(rng() % 201) - 100);
                for(int j=0; j<m; ++j) b.push_back((int)(rng() % 201) - 100);
                break;
            case 10: // 综合：长短不一的随机序列
                n = 10; m = 50;
                for(int j=0; j<n; ++j) a.push_back((int)(rng() % 100));
                for(int j=0; j<m; ++j) b.push_back((int)(rng() % 100));
                break;
        }

        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        write_file(i, a, b);
        cout << "Generated Case " << i << ": n=" << n << ", m=" << m << endl;
    }

    return 0;
}

测试点详细说明表

如何使用：

1. 将上述代码保存为 gen.cpp。
2. 使用 g++ gen.cpp -o gen -O2 -std=c++14 编译。
3. 运行 ./gen，当前目录下会生成 1.in ~ 10.out 共 20 个文件。
4. 将这些文件打包上传至你的 OJ 题目后台即可。

复杂度说明：

• 生成时间复杂度：$O(T \times (N \log N + M \log M))$，其中 $T=10$。在本题规模下，运行时间 $< 0.1s$。
• 空间复杂度：$O(N+M)$，用于存储临时向量，内存占用极低。
• 安全性：所有生成逻辑均为线性，不涉及递归或除法，杜绝了爆栈和除零风险。

在 NOI 竞赛中，链表题目通常考察的是指针操作的鲁棒性以及对内存空间的理解。我们将从最直观的“存入数组再排序”法，逐步进化到最优的“原地迭代合并”法。

版本一：暴力模拟法（数组中转排序）

思路： 既然是合并两个有序序列，最简单的办法就是不管它的链表结构，把所有元素扔进一个容器里，排序后重新构造。

• 时间复杂度： $O((N+M) \log (N+M))$ —— 主要开销在排序。
• 空间复杂度： $O(N+M)$ —— 需要额外数组存储所有节点值。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// NOI 竞赛中建议手写结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int main() {
    int n, m;
    vector<int> vals;

    // 读取第一个链表
    if (cin >> n) {
        for (int i = 0; i < n; ++i) {
            int x; cin >> x;
            vals.push_back(x);
        }
    }

    // 读取第二个链表
    if (cin >> m) {
        for (int i = 0; i < m; ++i) {
            int x; cin >> x;
            vals.push_back(x);
        }
    }

    // 1. 暴力排序
    sort(vals.begin(), vals.end());

    // 2. 输出结果（NOI 格式要求空格分隔）
    for (int i = 0; i < vals.size(); ++i) {
        cout << vals[i] << (i == vals.size() - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

版本二：递归实现（优雅但存在栈溢出风险）

思路： 比较两个链表的头结点，较小的节点作为合并后的头，其 next 指向“剩下的部分合并后的结果”。

• 时间复杂度： $O(N+M)$ —— 每个节点只访问一次。
• 空间复杂度： $O(N+M)$ —— 易错点：递归深度为 $N+M$，在 NOI 竞赛中如果数据规模达到 $10^6$，会导致 Segmentation Fault (栈溢出)。

#include <iostream>

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

// 递归函数：逻辑清晰，但消耗系统栈空间
ListNode* mergeRecursive(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;

    if (l1->val <= l2->val) {
        l1->next = mergeRecursive(l1->next, l2);
        return l1;
    } else {
        l2->next = mergeRecursive(l1, l2->next);
        return l2;
    }
}

// 辅助函数：按题意格式读取并构建链表
ListNode* buildList(int len) {
    if (len <= 0) return nullptr;
    int val; cin >> val;
    ListNode* head = new ListNode(val);
    ListNode* cur = head;
    for (int i = 1; i < len; ++i) {
        cin >> val;
        cur->next = new ListNode(val);
        cur = cur->next;
    }
    return head;
}

int main() {
    int n, m;
    ListNode *l1 = nullptr, *l2 = nullptr;

    if (cin >> n) l1 = buildList(n);
    if (cin >> m) l2 = buildList(m);

    ListNode* res = mergeRecursive(l1, l2);

    // 输出
    while (res) {
        std::cout << res->val << (res->next ? " " : "");
        res = res->next;
    }
    return 0;
}

版本三：最优解 - 迭代双指针（NOI 推荐风格）

思路： 使用一个**虚拟头节点（Dummy Node）**来简化链表头部的处理，通过 while 循环比较并移动指针。

• 时间复杂度分析： 只需一次线性扫描，复杂度 $O(N+M)$。
• 空间复杂度分析： 仅使用了常数个指针变量，复杂度 $O(1)$。这是本题的最优解。

#include <iostream>

using namespace std;

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

// 迭代合并：竞赛推荐写法，稳定且节省内存
ListNode* mergeIterative(ListNode* l1, ListNode* l2) {
    // 关键点：创建一个虚拟头节点，避免讨论谁是第一个节点的复杂逻辑
    ListNode* dummy = new ListNode(-1); 
    ListNode* prev = dummy;

    while (l1 != nullptr && l2 != nullptr) {
        if (l1->val <= l2->val) {
            prev->next = l1; // 将较小的节点挂载到新链表末尾
            l1 = l1->next;   // 移动指针
        } else {
            prev->next = l2;
            l2 = l2->next;
        }
        prev = prev->next;
    }

    // 易错点：循环结束后，可能有一个链表还没走完
    // 直接把剩下的部分挂在后面即可，不需要再循环
    prev->next = (l1 == nullptr) ? l2 : l1;

    ListNode* head = dummy->next;
    delete dummy; // 竞赛中养成手动释放内存的好习惯
    return head;
}

// 辅助读取
ListNode* readList() {
    int len;
    if (!(cin >> len) || len <= 0) return nullptr;
    ListNode* head = nullptr, *tail = nullptr;
    for (int i = 0; i < len; ++i) {
        int x; cin >> x;
        ListNode* newNode = new ListNode(x);
        if (!head) head = tail = newNode;
        else {
            tail->next = newNode;
            tail = newNode;
        }
    }
    return head;
}

int main() {
    // 优化 IO 速度
    ios::sync_with_stdio(false);
    cin.tie(0);

    ListNode* l1 = readList();
    ListNode* l2 = readList();

    ListNode* result = mergeIterative(l1, l2);

    // 输出结果
    bool first = true;
    while (result) {
        if (!first) cout << " ";
        cout << result->val;
        first = false;
        result = result->next;
    }
    cout << endl;

    return 0;
}

教练的复杂度优化建议与总结

1. 为什么迭代优于递归？ 在 NOI 这种对内存和稳定性要求极高的竞赛中，递归产生的栈空间开销（Stack Overflow）是潜在的“炸弹”。迭代法虽然代码稍长，但空间稳定性最高。

2. 时间复杂度能更快吗？ 由于每个元素至少要被“看”一眼才能确定位置，所以 $O(N+M)$ 已经是该问题的理论下界，无法再优化。

3. 读题关键词与坑点：

   • 关键词“升序”：如果没有这两个字，题目难度将从 $O(N)$ 变为 $O(N \log N)$ 的排序问题。
   • 关键词“拼接原有节点”：提示你不要使用大量的 new 操作，而是修改指针的指向（next 赋值）。
   • 坑点：空链表。如果输入 0 个元素，程序必须能正确返回而不断句（即输出换行或空）。

4. 调试建议： 写链表题时，如果程序崩溃，通常是解引用了 nullptr。在写 p->next 前，务必确认 p 不是空指针。在版本三的代码中，while (l1 && l2) 完美避开了这个问题。