为了方便你快速创建 OJ 测试数据，我为你编写了这个全自动的数据生成器。它能够生成符合 NOI 规范的输入文件（.in）和输出文件（.out）。

数据生成器设计重点

1. 算法效率：生成器内置了 $O(N \log K)$ 的优先队列合并算法来产生 .out 文件，确保生成大数据集时不会超时。
2. 数据分布：
   • 边界测试：$K=0$、所有链表为空、只有一个链表、每个链表只有一个节点等。
   • 压力测试：最大 $K$ 值与最大 $N$ 值，用于区分 $O(NK)$ 和 $O(N \log K)$ 算法。
   • 特殊数值：全相同数值、不重叠区间、深度重叠区间、极端正负值。
3. 安全性：使用 mt19937 随机数引擎，不使用递归，防止爆栈。

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

using namespace std;

// === 标准答案逻辑：用于产生 .out 文件 ===
// 使用优先队列实现多路归并，复杂度 O(N log K)
struct Node {
    int val;
    int listIdx;
    int elementIdx;
    bool operator>(const Node& other) const {
        return val > other.val;
    }
};

void generate_output(string out_name, int k, const vector<vector<int>>& lists) {
    ofstream fout(out_name);
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    
    int total_nodes = 0;
    for (int i = 0; i < k; ++i) {
        if (!lists[i].empty()) {
            pq.push({lists[i][0], i, 0});
        }
        total_nodes += lists[i].size();
    }

    bool first = true;
    while (!pq.empty()) {
        Node top = pq.top();
        pq.pop();

        if (!first) fout << " ";
        fout << top.val;
        first = false;

        if (top.elementIdx + 1 < (int)lists[top.listIdx].size()) {
            pq.push({lists[top.listIdx][top.elementIdx + 1], top.listIdx, top.elementIdx + 1});
        }
    }
    if (total_nodes > 0) fout << endl;
    fout.close();
}

// === 数据生成器核心 ===
void save_case(int id, int k, vector<vector<int>>& lists) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";

    // 写入 .in
    ofstream fin(in_name);
    fin << k << "\n";
    for (int i = 0; i < k; ++i) {
        fin << lists[i].size();
        for (int val : lists[i]) fin << " " << val;
        fin << "\n";
    }
    fin.close();

    // 产生 .out
    generate_output(out_name, k, lists);
    cout << "Test Case " << id << " generated: K=" << k << endl;
}

int main() {
    mt19937 rng(114514); // 固定种子

    for (int t = 1; t <= 10; ++t) {
        int k = 0;
        vector<vector<int>> lists;

        if (t == 1) { // 边界：K=0
            k = 0;
        } else if (t == 2) { // 边界：K>0 但全是空链表
            k = 10;
            lists.resize(k);
        } else if (t == 3) { // 边界：只有一个链表
            k = 1;
            lists.push_back({-100, 0, 100});
        } else if (t == 4) { // 边界：每个链表只有一个节点 (K=N)
            k = 500;
            for(int i=0; i<k; ++i) lists.push_back({(int)(rng() % 20000) - 10000});
        } else if (t == 5) { // 特殊：所有数值完全相同
            k = 50;
            for(int i=0; i<k; ++i) lists.push_back(vector<int>(50, 666));
        } else if (t == 6) { // 特殊：区间完全不重叠 (List1 < List2 < List3)
            k = 100;
            int start = -10000;
            for(int i=0; i<k; ++i) {
                vector<int> v;
                for(int j=0; j<10; ++j) v.push_back(start++);
                lists.push_back(v);
            }
        } else if (t == 7) { // 典型：稀疏的长链表
            k = 10;
            for(int i=0; i<k; ++i) {
                vector<int> v;
                for(int j=0; j<1000; ++j) v.push_back((int)(rng() % 20000) - 10000);
                sort(v.begin(), v.end());
                lists.push_back(v);
            }
        } else if (t == 8) { // 典型：短链表高度交错
            k = 1000;
            for(int i=0; i<k; ++i) {
                vector<int> v;
                for(int j=0; j<10; ++j) v.push_back((int)(rng() % 1000));
                sort(v.begin(), v.end());
                lists.push_back(v);
            }
        } else if (t == 9) { // 压力：最大 K 与 最大 N 组合
            k = 5000;
            for(int i=0; i<k; ++i) {
                vector<int> v = {(int)(rng() % 20000) - 10000, (int)(rng() % 20000) - 10000};
                sort(v.begin(), v.end());
                lists.push_back(v);
            }
        } else if (t == 10) { // 综合：随机分布
            k = 200;
            for(int i=0; i<k; ++i) {
                int len = rng() % 100;
                vector<int> v;
                for(int j=0; j<len; ++j) v.push_back((int)(rng() % 20000) - 10000);
                sort(v.begin(), v.end());
                lists.push_back(v);
            }
        }
        
        save_case(t, k, lists);
    }
    return 0;
}

测试点覆盖说明：

给 OJ 管理者的建议：

1. 文件大小：总共 10 个测试点，总节点数为 $N \le 10,000$。这意味着每个 .in 和 .out 文件约在几十 KB，总数据包大小约为 1MB，非常适合上传和分发。
2. 时间限制：由于 $N=10^4$，$O(N \log K)$ 的解法在 1.0s 内绰绰有余（约需 0.01s），而写挂了的 $O(NK)$ 在测试点 8、9 中可能会感觉到明显的卡顿。
3. 内存限制：128MB 对本题来说非常宽裕，但在创建测试数据时，通过 new 创建的节点如果没有 delete，在 Case 9 这种多次操作中应注意内存泄露（虽然进程结束会回收，但这是个好的竞赛习惯）。

在 NOI 竞赛中，处理“多路归并”问题有三种境界：从最简单的全数据排序，到分治两两合并，再到最优的优先队列（堆）优化。

下面我将为你依次展示这三个版本的完整代码。

版本一：辅助容器排序法（简单暴力）

思路思考： 最直接的想法是不管链表结构，把所有节点的值全部读取到一个 vector 中，利用 std::sort（快排）进行排序，最后重新串成一个新的链表。

• 时间复杂度分析：$O(N \log N)$。其中 $N$ 是总节点数。排序是瓶颈。
• 空间复杂度分析：$O(N)$。需要额外空间存储所有节点值。
• 评价：在 $N=10^4$ 的规模下，这个方法非常稳，且代码量极小，不容易写错。

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

using namespace std;

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

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

    int k;
    if (!(cin >> k)) return 0;

    vector<int> all_vals;
    for (int i = 0; i < k; ++i) {
        int n; cin >> n;
        for (int j = 0; j < n; ++j) {
            int v; cin >> v;
            all_vals.push_back(v);
        }
    }

    if (all_vals.empty()) return 0;

    // 全局排序
    sort(all_vals.begin(), all_vals.end());

    // 重新构造输出（竞赛中可以直接输出，不一定要真的建链表，但这里展示建表逻辑）
    for (int i = 0; i < all_vals.size(); ++i) {
        cout << all_vals[i] << (i == all_vals.size() - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

版本二：分治合并法（Divide and Conquer）

思路思考： 模仿归并排序。将 $k$ 个链表分成两半，分别合并左边一半和右边一半，最后将两个合并好的长链表进行“二路归并”。

• 时间复杂度分析：$O(N \log k)$。每层合并总节点数为 $N$，共 $\log k$ 层。
• 空间复杂度分析：$O(\log k)$。递归调用的系统栈深度。
• 评价：逻辑优美，避开了复杂的堆操作，但在链表极多且长度极短时，递归开销略大。

#include <iostream>
#include <vector>

using namespace std;

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

// 基础：合并两个有序链表 (二路归并)
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;
}

// 分治：将 lists[left...right] 合并为一个
ListNode* solve(vector<ListNode*>& lists, int left, int right) {
    if (left == right) return lists[left];
    if (left > right) return nullptr;
    int mid = (left + right) >> 1;
    ListNode* l1 = solve(lists, left, mid);
    ListNode* l2 = solve(lists, mid + 1, right);
    return mergeTwoLists(l1, l2);
}

int main() {
    int k; cin >> k;
    vector<ListNode*> lists(k);
    for (int i = 0; i < k; ++i) {
        int n; cin >> n;
        ListNode* head = nullptr, *cur = nullptr;
        for (int j = 0; j < n; ++j) {
            int v; cin >> v;
            ListNode* node = new ListNode(v);
            if (!head) head = cur = node;
            else { cur->next = node; cur = node; }
        }
        lists[i] = head;
    }

    ListNode* res = solve(lists, 0, k - 1);
    while (res) {
        cout << res->val << (res->next ? " " : "");
        res = res->next;
    }
    return 0;
}

版本三：优先队列法（最优复杂度解法）

思路思考： 维护一个大小为 $k$ 的最小堆，堆中存放每个链表当前待处理的头节点。每次取出堆顶（最小值），然后将该节点的下一个节点放入堆中。

• 时间复杂度分析：$O(N \log k)$。每个节点进出堆一次，操作复杂度 $\log k$。
• 空间复杂度分析：$O(k)$。堆的大小始终不超过 $k$。
• 关键点：std::priority_queue 默认是大根堆。要实现小根堆，需要自定义比较结构体，且符号要写成 >。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

// 易错点：自定义比较函数
// priority_queue 是最大堆，为了得到最小堆，我们要定义 a > b 时返回 true
struct CompareNode {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val; 
    }
};

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

    int k;
    if (!(cin >> k)) return 0;

    // 最小堆，存储节点指针
    priority_queue<ListNode*, vector<ListNode*>, CompareNode> pq;

    for (int i = 0; i < k; ++i) {
        int n; cin >> n;
        ListNode* head = nullptr, *cur = nullptr;
        for (int j = 0; j < n; ++j) {
            int v; cin >> v;
            ListNode* node = new ListNode(v);
            if (!head) head = cur = node;
            else { cur->next = node; cur = node; }
        }
        // 关键点：只有非空链表才入堆
        if (head) pq.push(head);
    }

    ListNode dummy(0);
    ListNode* tail = &dummy;

    while (!pq.empty()) {
        ListNode* node = pq.top(); // 获取当前最小节点
        pq.pop();

        tail->next = node; // 接入结果链表
        tail = node;

        if (node->next) {
            pq.push(node->next); // 将该链表的下一个节点压入堆
        }
    }

    // 输出
    ListNode* p = dummy.next;
    while (p) {
        cout << p->val << (p->next ? " " : "");
        p = p->next;
    }
    cout << endl;

    return 0;
}

教练的复杂度优化建议

1. 内存管理（Static Array 技巧）： 在 NOI 中，频繁 new 节点会导致内存碎片且速度较慢。如果 $N=10^6$，建议使用静态数组模拟链表：

   struct Node { int val, nxt; } pool[MAXN];
   int head[MAXK], tot;
   

   这样分配内存只是 tot++，效率极高。

2. 空间优化： 版本三的空间复杂度 $O(k)$ 是最优的。如果 $k$ 特别大（如 $10^6$）而内存只有 128MB，要注意堆的大小。

3. 时间优化建议：

   • 读入优化：链表题通常数据量大，使用 fread 快读可以显著减少耗时。
   • 堆的选择：在 C++ 中 std::priority_queue 已经足够快。但在某些特殊场景（如频繁修改堆中元素），手写二叉堆或使用配对堆可能更快。

总结

• 版本一适合比赛中快速拿分（如果不卡时间）。
• 版本二展示了分治思想，是理解归并排序的最佳实践。
• 版本三是工业界和竞赛中的标准解法，必须熟练掌握 priority_queue 的自定义比较写法。