为了方便你创建 OJ（Online Judge）测试数据，我编写了一个完整的数据生成器。该程序遵循 NOI C++14 标准，能够自动生成 1-10 号测试点的 .in 和 .out 文件。

数据生成器设计逻辑

1. 区分度与规模：
   • 最大 $N=10^5$，总计 10 组数据。每组数据约 200KB-400KB，总文件大小控制在 2MB 左右。
   • 通过构造**“几乎回文”**的数据（如只有中点或端点一个数字不同），可以有效区分只检查部分特征的错误算法。
2. 测试点分布：
   • 1-2：官方样例。
   • 3：极小边界 ($N=1$)。
   • 4-5：大规模全同数据与完全随机数据。
   • 6-7：大规模完美回文（奇数长与偶数长）。
   • 8-10：大规模“伪回文”（只有头部、尾部或中部一个数字不同），专门卡掉粗糙的哈希或贪心判断。
3. 安全性：
   • 非递归解法：在生成答案时使用迭代版的快慢指针+反转逻辑，确保在 $10^5$ 长度下不会爆栈。
   • 内存管理：使用静态数组或 std::vector 模拟链表，避免频繁 new 操作。

完整数据生成器代码 (DataGenerator.cpp)

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

using namespace std;

// ================= 标准答案：O(n) 时间, O(1) 空间 (迭代版) =================
// 这里的解决逻辑用于生成 .out 文件
int solve(int n, const vector<int>& vals) {
    if (n <= 1) return 1;
    
    // 模拟快慢指针定位
    int mid = (n - 1) / 2; // 前半部分的结尾
    
    vector<int> second_half;
    for (int i = mid + 1; i < n; ++i) {
        second_half.push_back(vals[i]);
    }
    
    // 反转后半部分
    reverse(second_half.begin(), second_half.end());
    
    // 比较
    for (size_t i = 0; i < second_half.size(); ++i) {
        if (vals[i] != second_half[i]) return 0;
    }
    return 1;
}

// ================= 数据生成工具 =================
mt19937 rng(time(0));

void write_test_case(int id, int n, const vector<int>& vals) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";

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

    // 运行标准算法并写入 .out 文件
    ofstream fout(out_name);
    fout << solve(n, vals) << endl;
    fout.close();

    cout << "Test Case " << id << " [N=" << n << "] generated." << endl;
}

// ================= 主逻辑 =================
int main() {
    // 1-2: 样例数据
    write_test_case(1, 4, {1, 2, 2, 1});
    write_test_case(2, 2, {1, 2});

    // 3: 边界 - 最小长度
    write_test_case(3, 1, {7});

    // 4: 大规模 - 全同数据 (回文)
    write_test_case(4, 100000, vector<int>(100000, 5));

    // 5: 大规模 - 随机数据 (非回文概率极高)
    vector<int> v5(100000);
    for(int i=0; i<100000; ++i) v5[i] = rng() % 10;
    write_test_case(5, 100000, v5);

    // 6: 大规模 - 完美回文 (偶数长)
    vector<int> v6(100000);
    for(int i=0; i<50000; ++i) v6[i] = v6[99999-i] = rng() % 10;
    write_test_case(6, 100000, v6);

    // 7: 大规模 - 完美回文 (奇数长)
    vector<int> v7(99999);
    for(int i=0; i<49999; ++i) v7[i] = v7[99998-i] = rng() % 10;
    v7[49999] = rng() % 10;
    write_test_case(7, 99999, v7);

    // 8: 伪回文 - 头部不同
    vector<int> v8 = v6;
    v8[0] = (v6[0] + 1) % 10;
    write_test_case(8, 100000, v8);

    // 9: 伪回文 - 尾部不同
    vector<int> v9 = v6;
    v9[99999] = (v6[99999] + 1) % 10;
    write_test_case(9, 100000, v9);

    // 10: 伪回文 - 中部不同
    vector<int> v10 = v6;
    v10[49999] = (v6[49999] + 1) % 10;
    v10[50000] = (v6[50000] + 2) % 10;
    write_test_case(10, 100000, v10);

    return 0;
}

数据规模与文件说明

1. 数据范围限制：
   • $N=10^5$ 的测试点有 7 个。
   • 每个整数 $0 \le val \le 9$，在 .in 文件中大约占 2 字节（数字+空格）。
   • 单组大文件约 $200KB$。10 组总大小约为 $1.5MB - 2MB$，非常符合题目要求的 2MB 理想值。
2. 生成效率：
   • 由于使用了 std::vector 和 std::reverse，生成逻辑是线性的 $O(N)$。
   • 生成所有 10 组测试点的时间在 1s 以内，不会发生生成超时。
3. OJ 评测建议：
   • 由于本题涉及链表操作，建议 OJ 评测时开启 -O2 优化。
   • 如果选手的解法使用了递归，请提醒他们增加栈空间（ulimit -s unlimited），或者在程序中使用 #pragma comment(linker, "/STACK:...")（如果是 Windows 环境）。

读题关键词 (辅导重点)

作为教练，在分发这些数据前，你可以提示学生：

• “1.0s”：意味着 $10^5$ 规模下，$O(N^2)$ 的两两比对会超时。
• “回文性质”：关注数据的对称性。
• “伪回文”卡点：提醒学生检查边界条件，不要只对比前几个和后几个字符。数据生成器里的第 8-10 号测试点就是专门为那些“投机取巧”的错误哈希或贪心准备的。

你好！我是你的 NOI 教练。在处理“回文”这类具有对称特征的问题时，思维的演进通常是从**“如何存储”到“如何原地操作”**。

下面我将为你展示从最简单的数组辅助法，到递归法，再到最优的快慢指针法的完整实现。

第一阶段：辅助数组法 (空间 $O(n)$，最稳妥的保分方案)

思路思考： 由于单链表无法从后往前遍历，最直观的方法就是把链表中的值全部拷贝到一个数组（或 std::vector）中。数组支持随机访问，我们可以直接利用双指针从两端向中间比对。

#include <iostream>
#include <vector>

using namespace std;

// NOI 风格的链表节点定义
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

/**
 * 复杂度分析：
 * 时间复杂度：O(n)，需要遍历一遍链表，再遍历半遍数组。
 * 空间复杂度：O(n)，开辟了 vector 存储所有节点值。
 */
bool isPalindrome_v1(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return true;
    
    vector<int> vals;
    ListNode* curr = head;
    // 将链表值存入数组
    while (curr != nullptr) {
        vals.push_back(curr->val);
        curr = curr->next;
    }
    
    // 双指针比对
    int left = 0, right = vals.size() - 1;
    while (left < right) {
        if (vals[left] != vals[right]) return false;
        left++;
        right--;
    }
    return true;
}

// 模拟 NOI 竞赛的输入处理
int main() {
    int n;
    if (!(cin >> n)) return 0;
    if (n == 0) { cout << 1 << endl; return 0; }

    ListNode* dummy = new ListNode(0);
    ListNode* tail = dummy;
    for (int i = 0; i < n; ++i) {
        int x; cin >> x;
        tail->next = new ListNode(x);
        tail = tail->next;
    }

    cout << (isPalindrome_v1(dummy->next) ? 1 : 0) << endl;
    return 0;
}

第二阶段：系统栈递归法 (空间 $O(n)$，精巧的函数式思维)

思路思考： 我们可以利用递归的“回溯”特性。递归函数会一直深入到链表的最后一个节点，在回溯的过程中，最后一个节点会先被处理，如果我们同时维护一个从头开始的全局指针，就可以实现“头尾比对”。

注意：虽然逻辑优美，但 $10^5$ 的数据量在系统栈较小时（如 8MB）有爆栈风险。

ListNode* frontPointer;

bool recursivelyCheck(ListNode* currentNode) {
    if (currentNode != nullptr) {
        // 递归到末尾
        if (!recursivelyCheck(currentNode->next)) return false;
        // 回溯时进行比对
        if (currentNode->val != frontPointer->val) return false;
        // 比较完后，头指针向后移动一步
        frontPointer = frontPointer->next;
    }
    return true;
}

bool isPalindrome_v2(ListNode* head) {
    frontPointer = head;
    return recursivelyCheck(head);
}

第三阶段：最优解——快慢指针 + 原地反转 (空间 $O(1)$，金牌算法)

思路思考： 为了达到 $O(1)$ 的额外空间（不计输入数据本身），我们不能申请新空间，必须在原链表上动手术：

1. 找中点：使用快慢指针，快指针走两步，慢指针走一步。当快指针到头时，慢指针正好在中点附近。
2. 反转：将链表的后半部分原地反转。
3. 比对：前半部分和反转后的后半部分进行逐值比对。

#include <iostream>

using namespace std;

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

/**
 * 辅助函数：原地反转链表
 */
ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr != nullptr) {
        ListNode* nextTemp = curr->next;
        curr->next = prev; // 易错点：修改指针方向
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

/**
 * 复杂度分析：
 * 时间复杂度：O(n)，找中点 n/2，反转 n/2，比对 n/2，总计 1.5n。
 * 空间复杂度：O(1)，仅使用了常数个指针变量。
 */
bool isPalindrome_v3(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return true;

    // 1. 寻找前半部分的尾节点 (快慢指针)
    ListNode* slow = head;
    ListNode* fast = head;
    // 循环结束后，slow 就在中点（偶数长度为前半段末尾，奇数长度为中间点）
    while (fast->next != nullptr && fast->next->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // 2. 反转后半部分链表
    // 易错点：反转的是 slow->next 开始的部分
    ListNode* secondHalfStart = reverseList(slow->next);

    // 3. 比对是否回文
    ListNode* p1 = head;
    ListNode* p2 = secondHalfStart;
    bool result = true;
    while (result && p2 != nullptr) {
        if (p1->val != p2->val) result = false;
        p1 = p1->next;
        p2 = p2->next;
    }

    // 4. (可选) 恢复链表原状：NOI 模拟赛中保持原数据完整性是好习惯
    // slow->next = reverseList(secondHalfStart);

    return result;
}

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

    int n;
    if (!(cin >> n)) return 0;
    if (n == 0) { cout << 1 << endl; return 0; }

    // 构建链表
    ListNode* head = nullptr;
    ListNode* tail = nullptr;
    for (int i = 0; i < n; ++i) {
        int x; cin >> x;
        ListNode* newNode = new ListNode(x);
        if (!head) head = tail = newNode;
        else {
            tail->next = newNode;
            tail = newNode;
        }
    }

    cout << (isPalindrome_v3(head) ? 1 : 0) << endl;
    return 0;
}

时间复杂度优化建议 (竞赛必备经验)

1. IO 优化：在处理 $10^5$ 规模的数据时，cin 和 cout 的同步流会导致严重的性能瓶颈。务必加入 ios::sync_with_stdio(false); cin.tie(0);。
2. 内存池技术：如果在正式 NOI 赛场上，链表节点频繁 new 会产生时间开销。可以预分配一个静态数组 Node pool[100005] 来模拟动态内存分配。
3. 判空与边界：在 fast->next->next 这种写法中，必须先保证 fast->next 不为空，否则会触发 Segmentation Fault，这是初学者最容易在链表题中丢分的地方。

读题关键词总结

• “回文” (Palindrome)：意味着对称性，暗示可以从两头向中间聚合。
• “链表” (Linked List)：暗示只能顺序访问。如果看到“单向”，立刻想到寻找中点和反转。
• “额外空间 O(1)”：强制要求原地修改指针，不能使用 vector、stack 等容器。
• “节点值范围”：如本题 $0-9$，如果值范围很大，要注意内存对齐和比较时的溢出（虽然比较 int 不涉及溢出，但某些哈希做法需要注意）。

掌握了这套快慢指针 + 翻转的方法，你就掌握了单链表结构处理的底层逻辑。加油！