为了方便你创建 OJ (Online Judge) 测试数据，我为你编写了一个基于 C++14 标准的数据生成器。

该生成器会生成 10 组测试点，涵盖了空链表、单节点、最大数据范围、全相同数值、正负数交替等各种边界情况。为了符合 NOI 规范，生成器会直接生成 .in 文件，并调用内置的“标准答案逻辑”生成对应的 .out 文件。

数据生成器代码 (gen.cpp)

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

using namespace std;

// 定义数据范围
const int MAXN = 5000;
const int MAXVAL = 5000;
const int MINVAL = -5000;

// 标准答案逻辑：用于生成 .out 文件
// 使用迭代法，确保生成答案时不会爆栈
void solve(const vector<int>& input, string out_name) {
    ofstream fout(out_name);
    if (input.empty()) {
        fout << "" << endl; // 空链表输出空行
        return;
    }
    vector<int> output = input;
    reverse(output.begin(), output.end());
    
    for (int i = 0; i < output.size(); ++i) {
        fout << output[i] << (i == output.size() - 1 ? "" : " ");
    }
    fout << endl;
    fout.close();
}

// 写入输入文件
void write_input(const vector<int>& input, string in_name) {
    ofstream fin(in_name);
    for (int i = 0; i < input.size(); ++i) {
        fin << input[i] << (i == input.size() - 1 ? "" : " ");
    }
    fin << endl;
    fin.close();
}

int main() {
    // 使用随机设备初始化种子
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    
    for (int t = 1; t <= 10; ++t) {
        string in_name = to_string(t) + ".in";
        string out_name = to_string(t) + ".out";
        vector<int> data;
        
        // 针对不同测试点构造数据
        if (t == 1) { // 边界条件：空链表
            // data is empty
        } else if (t == 2) { // 边界条件：只有一个节点
            data.push_back(rng() % (MAXVAL - MINVAL + 1) + MINVAL);
        } else if (t == 3) { // 边界条件：只有两个节点
            data.push_back(1);
            data.push_back(2);
        } else if (t == 4) { // 满数据：顺序数据
            for (int i = 1; i <= MAXN; ++i) data.push_back(i);
        } else if (t == 5) { // 满数据：逆序数据
            for (int i = MAXN; i >= 1; --i) data.push_back(i);
        } else if (t == 6) { // 满数据：全相同数值
            int val = (int)(rng() % 100);
            for (int i = 0; i < MAXN; ++i) data.push_back(val);
        } else if (t == 7) { // 满数据：正负交替
            for (int i = 0; i < MAXN; ++i) {
                data.push_back(i % 2 == 0 ? 5000 : -5000);
            }
        } else if (t == 8) { // 随机数据：小规模
            int n = 100;
            uniform_int_distribution<int> dist(MINVAL, MAXVAL);
            for (int i = 0; i < n; ++i) data.push_back(dist(rng));
        } else if (t == 9) { // 随机数据：中等规模
            int n = 2500;
            uniform_int_distribution<int> dist(MINVAL, MAXVAL);
            for (int i = 0; i < n; ++i) data.push_back(dist(rng));
        } else if (t == 10) { // 随机数据：最大规模
            int n = MAXN;
            uniform_int_distribution<int> dist(MINVAL, MAXVAL);
            for (int i = 0; i < n; ++i) data.push_back(dist(rng));
        }

        // 生成文件
        write_input(data, in_name);
        solve(data, out_name);
        
        cout << "Generated Test Case " << t << ": n=" << data.size() << endl;
    }
    
    return 0;
}

测试点说明表格

数据生成器设计细节说明

1. 性能与大小优化：

   • 文件大小：即使在 $n=5000$ 的情况下，每个数字加上空格约为 6 字节，每个文件大小约为 30KB。10 组数据总大小约 600KB，远低于 2MB 的要求，适合网络传输和 OJ 评测。
   • 非递归生成：生成 .out 文件时使用了 std::reverse (本质是迭代)，避免了在生成超大规模测试数据时因系统栈限制导致的崩溃。

2. 安全性设计：

   • 无除零风险：代码中不涉及除法运算。
   • 内存管理：使用 std::vector 动态管理内存，避免了手动申请内存导致的泄漏。

3. OJ 适配性：

   • 输入格式：按照 LeetCode 的逻辑，输入为一系列整数。在 NOI 环境下，通常可以直接通过 while(cin >> x) 读入。生成器确保每个测试点末尾有且仅有一个换行符。
   • 随机性：使用了 std::mt19937 引擎。这比传统的 rand() 拥有更长的随机周期和更好的统计特性，能生成更具破坏性的随机分布。

如何使用

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

同学你好！在 NOI 竞赛中，虽然我们追求代码的极致效率，但稳扎稳打、从简单逻辑演进到最优算法是避免考场失误的重要方法。

下面我为你展示这道题的三个版本，分别对应不同的思维阶段。

版本一：辅助空间法 (最直观、保底方案)

思路分析： 如果你在考场上由于紧张，一时间无法理清指针交换的顺序，最稳妥的方法是“空间换时间”。利用 std::vector 或数组按顺序存储节点值，然后倒序重新赋值或构造。

• 时间复杂度：$O(n)$，遍历两次。
• 空间复杂度：$O(n)$，需要一个数组存节点。
• 评价：在 $N=5000$ 且内存限制 256MB 的情况下，此法完全能过，是考场上的保底策略。

#include <iostream>
#include <vector>

using namespace std;

// NOI风格的结构体定义
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverseList(ListNode* head) {
    if (!head) return nullptr;
    
    vector<int> vals;
    ListNode* curr = head;
    
    // 1. 将链表值存入辅助数组
    while (curr) {
        vals.push_back(curr->val);
        curr = curr->next;
    }
    
    // 2. 倒序写回原链表 (或者创建新链表)
    curr = head;
    for (int i = vals.size() - 1; i >= 0; i--) {
        curr->val = vals[i];
        curr = curr->next;
    }
    
    return head;
}

int main() {
    // 模拟NOI输入环境
    int x;
    ListNode* dummy = new ListNode(0);
    ListNode* tail = dummy;
    
    while (cin >> x) {
        tail->next = new ListNode(x);
        tail = tail->next;
        if (cin.get() == '\n') break; // 简单处理单行输入
    }
    
    ListNode* res = reverseList(dummy->next);
    
    // 输出结果
    while (res) {
        cout << res->val << (res->next ? " " : "");
        res = res->next;
    }
    cout << endl;
    return 0;
}

版本二：递归法 (分治思想)

思路分析： 运用“数学归纳法”。假设 head 之后的链表已经全部反转好了，我们只需要把 head 挂在反转后链表的末尾即可。

• 时间复杂度：$O(n)$，每个节点被访问一次。
• 空间复杂度：$O(n)$，主要的开销是递归产生的系统栈空间。
• 易错点：递归终止条件必须包含 head == nullptr 和 head->next == nullptr。

#include <iostream>

using namespace std;

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

ListNode* reverseList(ListNode* head) {
    // 递归边界：空节点或只有一个节点时，无需反转
    if (!head || !head->next) {
        return head;
    }
    
    // 递去：先反转后面的链表
    ListNode* newHead = reverseList(head->next);
    
    // 归来：此时 head->next 是反转后链表的“尾巴”
    // 易错点：让“尾巴”指向自己
    head->next->next = head;
    
    // 关键点：切断原有的指向，防止链表成环
    head->next = nullptr;
    
    return newHead;
}

// main 函数与版本一类似，略...

版本三：迭代法 (最优复杂度版本 - 推荐)

思路分析： 使用三指针通过一次遍历完成“原地翻转”。这是 NOI 考场上最希望看到的写法。

• 时间复杂度：$O(n)$，仅需遍历一次。
• 空间复杂度：$O(1)$，仅需三个指针变量。
• 关键点：在断开 curr->next 之前，必须先用临时变量保存下一个节点的位置。

#include <iostream>

using namespace std;

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

/**
 * 核心逻辑：原地反转
 * prev: 已经反转好的部分
 * curr: 当前待处理节点
 */
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    
    while (curr != nullptr) {
        // 1. 暂存：备胎 nextTemp 记住未来的路
        ListNode* nextTemp = curr->next;
        
        // 2. 反转：将当前节点指向前任
        curr->next = prev;
        
        // 3. 漂移：全员向后移动一位
        prev = curr;    // 此时 prev 变成新链表的头
        curr = nextTemp; // curr 继续处理原链表剩余部分
    }
    
    // 循环结束时，curr 是 nullptr，prev 正好指向原链表的最后一个节点
    return prev;
}

int main() {
    // 优化：加快读入速度（NOI必备）
    ios::sync_with_stdio(false);
    cin.tie(0);

    int x;
    ListNode* head = nullptr;
    ListNode* tail = nullptr;

    // 读入逻辑：构造原始链表
    while (cin >> x) {
        ListNode* newNode = new ListNode(x);
        if (!head) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
        if (cin.get() == '\n') break;
    }

    // 调用最优反转算法
    head = reverseList(head);

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

    return 0;
}

七、 复杂度优化建议与考场技巧

1. 时间优化建议：

   • 虽然反转链表已经是 $O(n)$，但在 NOI 这种对常数敏感的比赛中，迭代法由于没有函数调用的开销（压栈/弹栈），其执行效率会比递归法高出 2-3 倍。
   • 在输入量巨大的题目中，使用 scanf 或自己编写 fast_read (快读) 函数。

2. 空间优化思考过程：

   • 当你发现算法中存在“保存所有数据”的行为（如版本一），应思考：是否可以只保留前后的局部信息？
   • 在本题中，我们发现反转某个节点只需要知道它的 prev 和 next。因此，可以用三个指针替代整个数组，将空间从 $O(n)$ 优化到 $O(1)$。

3. 内存安全性 (易错点)：

   • 成环风险：如果在反转时忘记将 head->next 置空，链表会变成 [1] <-> [2] 这种无限死循环，导致 TLE (超时) 或 MLE (栈溢出)。
   • 空指针检查：在操作 curr->next 之前，永远要问自己一句：curr 会不会是 nullptr？

4. 静态链表技巧： 在正式 NOI 比赛中，为了追求极致速度，很多选手不使用 new 动态分配内存（容易产生碎片），而是预先开一个大数组模拟内存池：

   struct Node {
       int val, next;
   } nodes[5005];
   int head, tot;
   

   这种写法在处理复杂数据结构（如树链剖分、Splay）时更为高效。