这是一个完整的 “重排链表” (Reorder List) 题目的数据生成器。

该生成器不使用复杂的链表指针操作来生成答案，而是利用**双指针（数组模拟）**的方法来生成标准输出。这是因为“重排链表”的结果在数学逻辑上等价于：依次取数组的 头部、尾部、头部+1、尾部-1... 这样做既快速又绝对正确，适合作为 Standard Solution (Std)。

数据点设计策略

为了确保测试的全面性，设计了 10 个测试点：

• #1, #2 (基础): 小数据，分别为奇数长度和偶数长度，用于人眼验证。
• #3, #4 (边界): $N=1$ 和 $N=2$ 的极小情况，测试程序是否会因为空指针或越界崩溃。
• #5 (中等): $N=100$，随机数据。
• #6 (顺序): $N=50000$，数据有序 ($1, 2, \dots, N$)，方便观察规律。
• #7 (逆序): $N=50000$，数据逆序 ($N, N-1, \dots, 1$)。
• #8 (常数): $N=50000$，所有数值相同，测试是否依赖数值差异。
• #9, #10 (压力): $N=50000$，大规模随机数据，分别测试奇数和偶数长度的性能。

Generator 代码 (gen_reorder.cpp)

请将以下代码保存为 gen_reorder.cpp，编译并运行即可生成所有数据文件。

#include <bits/stdc++.h>
using namespace std;

// ==========================================
// Part 1: 标准解答 (Standard Solution)
// 使用数组双指针模拟链表重排逻辑，生成 .out
// 逻辑等价于：L1 -> Ln -> L2 -> Ln-1 ...
// ==========================================
vector<int> solve(const vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return {};
    
    vector<int> res;
    // 双指针：i指向头，j指向尾
    int i = 0;
    int j = n - 1;
    
    while (i <= j) {
        // 1. 取头部
        res.push_back(nums[i]);
        i++;
        
        // 2. 取尾部 (检查是否已经取完了，防止奇数长度中间重复取)
        if (i <= j) {
            res.push_back(nums[j]);
            j--;
        }
    }
    return res;
}

// ==========================================
// Part 2: 数据生成器工具
// ==========================================
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int random_int(int L, int R) {
    return uniform_int_distribution<int>(L, R)(rng);
}

// 生成数据的主函数
void generate_case(int case_id) {
    int n;
    vector<int> a;

    switch (case_id) {
        case 1: // 【基础】奇数长度小数据
            n = 5;
            for(int i=1; i<=n; i++) a.push_back(i);
            break;
            
        case 2: // 【基础】偶数长度小数据
            n = 4;
            for(int i=1; i<=n; i++) a.push_back(i);
            break;
            
        case 3: // 【边界】极小 N=1
            n = 1;
            a.push_back(random_int(1, 100));
            break;
            
        case 4: // 【边界】极小 N=2
            n = 2;
            a.push_back(10); a.push_back(20);
            break;
            
        case 5: // 【中等】随机
            n = 100;
            for(int i=0; i<n; i++) a.push_back(random_int(1, 1000));
            break;
            
        case 6: // 【特殊】大规模顺序 (1, 2, 3...)
            n = 50000;
            for(int i=0; i<n; i++) a.push_back(i + 1);
            break;
            
        case 7: // 【特殊】大规模逆序 (N, N-1...)
            n = 50000;
            for(int i=0; i<n; i++) a.push_back(n - i);
            break;
            
        case 8: // 【特殊】大规模全部相同
            n = 50000;
            {
                int val = random_int(1, 100);
                for(int i=0; i<n; i++) a.push_back(val);
            }
            break;
            
        case 9: // 【压力】大规模随机 (奇数长度)
            n = 49999;
            for(int i=0; i<n; i++) a.push_back(random_int(0, 1000000));
            break;
            
        case 10: // 【压力】大规模随机 (偶数长度)
            n = 50000;
            for(int i=0; i<n; i++) a.push_back(random_int(0, 1000000));
            break;
            
        default:
            n = 10;
            for(int i=0; i<n; i++) a.push_back(i);
    }

    // ==========================================
    // 文件输出
    // ==========================================
    string in_file = to_string(case_id) + ".in";
    string out_file = to_string(case_id) + ".out";

    cout << "Generating Case " << case_id << " (N=" << n << ")..." << endl;

    // 1. 写入 .in
    ofstream fin(in_file);
    fin << n << "\n";
    for (int i = 0; i < n; ++i) {
        fin << a[i] << (i == n - 1 ? "" : " ");
    }
    fin << "\n";
    fin.close();

    // 2. 计算答案并写入 .out
    vector<int> ans = solve(a);
    
    ofstream fout(out_file);
    for (int i = 0; i < n; ++i) {
        fout << ans[i] << (i == n - 1 ? "" : " ");
    }
    fout << "\n";
    fout.close();
}

int main() {
    // 循环生成 10 个测试点
    for (int i = 1; i <= 10; ++i) {
        generate_case(i);
    }
    cout << "All test cases generated successfully!" << endl;
    return 0;
}

使用方法

1. 编译：g++ gen_reorder.cpp -o gen -std=c++14 -O2
2. 运行：./gen (Windows 下是 gen.exe)
3. 验证：
   • 打开 1.in 应看到 5 和 1 2 3 4 5。
   • 打开 1.out 应看到 1 5 2 4 3。
   • 打开 2.in 应看到 4 和 1 2 3 4。
   • 打开 2.out 应看到 1 4 2 3。

这套数据生成器通过数组模拟了复杂的链表重排过程，既保证了生成的答案绝对正确（作为 Standard Verification），又覆盖了题目要求的各种规模和奇偶性情况。

这段代码是算法竞赛（OI/ACM）和 LeetCode 等刷题平台中最通用的链表节点定义。下面是带有详细注释的版本，涵盖了语法细节和竞赛中的使用习惯。

// 万能头文件
// 在 OI/ACM 竞赛中，这个头文件包含了 C++ 标准库中几乎所有的头文件
// 优点：省去了写 #include <iostream>, #include <vector> 等的麻烦
// 缺点：编译时间稍长，且非标准（但在 GCC/G++ 编译器下通用）
#include <bits/stdc++.h>

using namespace std;

// 定义链表节点结构体 (struct)
// 在竞赛中，通常使用 struct 而不是 class，因为 struct 的成员默认是 public 的
// 方便我们在解题时直接通过 node->val 或 node->next 访问和修改数据
struct ListNode {
    int val;            // 数据域：当前节点存储的数值 (Value)
    ListNode *next;     // 指针域：指向链表中下一个节点的指针 (Next Pointer)

    // 构造函数 (Constructor)
    // 作用：方便我们在创建新节点时，直接一行代码完成初始化
    // 语法解析：
    // 1. ListNode(int x) : 函数名与结构体名相同，表示这是构造函数，接受一个整数 x
    // 2. : val(x), next(NULL) : 这是“初始化列表” (Initialization List)
    //    - val(x) 表示把参数 x 赋值给成员变量 val
    //    - next(NULL) 表示把指针 next 初始化为空 (NULL)
    //    - C++11 及以上标准建议使用 nullptr 代替 NULL，但在竞赛中 NULL 依然通用
    ListNode(int x) : val(x), next(NULL) {}
};

/**
 * 【使用演示】
 * 
 * 1. 如果没有构造函数，你需要这样写（麻烦）：
 *    ListNode* node = new ListNode;
 *    node->val = 10;
 *    node->next = NULL;
 * 
 * 2. 有了构造函数，你可以这样写（高效）：
 *    ListNode* node = new ListNode(10);
 */

👨‍🏫 教练补充讲解

1. 为什么是 struct？

   • 面向对象编程中常用 class 配合 private 做封装。但在算法竞赛中，为了写代码快，我们希望直接操作变量（比如 p->val = 5），不需要写 getVal() 或 setVal() 这种啰嗦的函数，所以 struct 是首选。

2. 初始化列表 : val(x), next(NULL)

   • 这不仅仅是简写，效率也更高。它表示在变量诞生的那一刻就赋予了初值，而不是先产生变量再进行赋值操作。

3. NULL vs nullptr

   • 代码中用的是 NULL（本质是整数 0）。
   • 因为题目要求 C++14 标准，实际上推荐使用 nullptr（空指针字面量），它比 NULL 更安全，能避免一些和整数混淆的奇怪 Bug。如果你在比赛中用 C++11 或更高版本，建议习惯写 nullptr。

符合 C++14 标准的 OI 竞赛风格定义

主要区别在于使用 nullptr 代替了 NULL。nullptr 是 C++11 引入、C++14 中广泛使用的空指针关键字，它比 NULL（通常被定义为整数 0）类型更安全，能避免重载函数时的歧义。

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;

    // C++14 标准构造函数
    // 1. 使用初始化列表 : val(x), next(nullptr)
    // 2. 必须使用 nullptr 而不是 NULL
    ListNode(int x) : val(x), next(nullptr) {}
};

为什么 C++14 推荐用 nullptr？

在旧标准中，NULL 其实就是 0。如果你有两个同名函数：

• void func(int a)
• void func(int* p)

调用 func(NULL) 可能会意外调用到 func(int a)，导致难以排查的 Bug。 而调用 func(nullptr) 则一定会调用 func(int* p)，这对指针操作频繁的链表题目非常重要。