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

数据生成器设计重点

1. 判定逻辑：在生成 .out 文件时，直接根据 $pos$ 的值判断。如果 $pos \neq -1$，则答案为 true，否则为 false。
2. 边界覆盖：
   • $n=0$：空链表。
   • $n=1$ 且无环。
   • $n=1$ 且有环（指向自己）。
   • $n=10^4$：最大数据规模。
   • 环在头部、环在尾部、环在中间。
3. 安全性：使用 mt19937 随机数引擎，确保数据分布均匀且可复现。

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

using namespace std;

/**
 * @brief 生成标准答案
 * 根据 pos 的值直接判定。OI 题目后台生成数据时，
 * 我们已知逻辑，直接根据输入参数生成结果最准确。
 */
string get_standard_answer(int pos) {
    return (pos != -1) ? "true" : "false";
}

/**
 * @brief 写入测试点文件
 */
void write_test_case(int id, int n, int pos, const vector<int>& vals) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";

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

    // 生成输出文件
    ofstream fout(out_name);
    fout << get_standard_answer(pos) << endl;
    fout.close();
}

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

    for (int i = 1; i <= 10; ++i) {
        int n = 0;
        int pos = -1;
        vector<int> vals;

        // 根据测试点 ID 分配不同的场景
        if (i == 1) { // 边界：空链表
            n = 0; pos = -1;
        } 
        else if (i == 2) { // 边界：单个节点无环
            n = 1; pos = -1;
            vals = {1};
        }
        else if (i == 3) { // 边界：单个节点有环 (指向自己)
            n = 1; pos = 0;
            vals = {1};
        }
        else if (i == 4) { // 场景：两个节点，环指向头
            n = 2; pos = 0;
            vals = {1, 2};
        }
        else if (i == 5) { // 场景：两个节点，无环
            n = 2; pos = -1;
            vals = {1, 2};
        }
        else if (i == 6) { // 场景：中等规模，环在中间
            n = 100; pos = 50;
            for(int j=0; j<n; ++j) vals.push_back((int)(rng() % 200000) - 100000);
        }
        else if (i == 7) { // 典型：大规模无环
            n = 10000; pos = -1;
            for(int j=0; j<n; ++j) vals.push_back((int)(rng() % 100));
        }
        else if (i == 8) { // 典型：大规模有环 (环在第一位)
            n = 10000; pos = 0;
            for(int j=0; j<n; ++j) vals.push_back((int)(rng() % 100));
        }
        else if (i == 9) { // 典型：大规模有环 (环在最后一位，即指向自己)
            n = 10000; pos = 9999;
            for(int j=0; j<n; ++j) vals.push_back((int)(rng() % 100));
        }
        else if (i == 10) { // 综合：大规模随机位置环
            n = 10000; pos = (int)(rng() % 10000);
            for(int j=0; j<n; ++j) vals.push_back((int)(rng() % 200000) - 100000);
        }

        // 补齐 vals (针对未手动赋值的情况)
        if (vals.empty() && n > 0) {
            for(int j=0; j<n; ++j) vals.push_back(j);
        }

        write_test_case(i, n, pos, vals);
        cout << "Generated Case " << i << ": n=" << n << ", pos=" << pos << endl;
    }

    return 0;
}

测试点覆盖说明表

如何配置到 OJ：

1. 编译生成器：g++ gen.cpp -o gen -std=c++14 -O2
2. 运行生成器：./gen
3. 上传数据：将产生的 1.in 到 10.out 共 20 个文件打包上传至你的 OJ 题目后台。

复杂度与规范说明：

• 文件大小：总节点数 $10^4$，包含数值，每个输入文件约 100KB。10 个测试点约 1MB，远低于 2MB 限制。
• 生成时间：全过程瞬间完成（< 0.1s），不存在超时风险。
• 非递归逻辑：生成器和答案判定均为线性循环，不会发生爆栈。
• 异常处理：已处理 $n=0$ 的情况；$pos$ 严格限制在 $[-1, n-1]$ 范围内，不存在除零或数组越界。

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

数据生成器设计重点

1. 判定逻辑：在生成 .out 文件时，直接根据 $pos$ 的值判断。如果 $pos \neq -1$，则答案为 true，否则为 false。
2. 边界覆盖：
   • $n=0$：空链表。
   • $n=1$ 且无环。
   • $n=1$ 且有环（指向自己）。
   • $n=10^4$：最大数据规模。
   • 环在头部、环在尾部、环在中间。
3. 安全性：使用 mt19937 随机数引擎，确保数据分布均匀且可复现。

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

using namespace std;

/**
 * @brief 生成标准答案
 * 根据 pos 的值直接判定。OI 题目后台生成数据时，
 * 我们已知逻辑，直接根据输入参数生成结果最准确。
 */
string get_standard_answer(int pos) {
    return (pos != -1) ? "true" : "false";
}

/**
 * @brief 写入测试点文件
 */
void write_test_case(int id, int n, int pos, const vector<int>& vals) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";

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

    // 生成输出文件
    ofstream fout(out_name);
    fout << get_standard_answer(pos) << endl;
    fout.close();
}

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

    for (int i = 1; i <= 10; ++i) {
        int n = 0;
        int pos = -1;
        vector<int> vals;

        // 根据测试点 ID 分配不同的场景
        if (i == 1) { // 边界：空链表
            n = 0; pos = -1;
        } 
        else if (i == 2) { // 边界：单个节点无环
            n = 1; pos = -1;
            vals = {1};
        }
        else if (i == 3) { // 边界：单个节点有环 (指向自己)
            n = 1; pos = 0;
            vals = {1};
        }
        else if (i == 4) { // 场景：两个节点，环指向头
            n = 2; pos = 0;
            vals = {1, 2};
        }
        else if (i == 5) { // 场景：两个节点，无环
            n = 2; pos = -1;
            vals = {1, 2};
        }
        else if (i == 6) { // 场景：中等规模，环在中间
            n = 100; pos = 50;
            for(int j=0; j<n; ++j) vals.push_back((int)(rng() % 200000) - 100000);
        }
        else if (i == 7) { // 典型：大规模无环
            n = 10000; pos = -1;
            for(int j=0; j<n; ++j) vals.push_back((int)(rng() % 100));
        }
        else if (i == 8) { // 典型：大规模有环 (环在第一位)
            n = 10000; pos = 0;
            for(int j=0; j<n; ++j) vals.push_back((int)(rng() % 100));
        }
        else if (i == 9) { // 典型：大规模有环 (环在最后一位，即指向自己)
            n = 10000; pos = 9999;
            for(int j=0; j<n; ++j) vals.push_back((int)(rng() % 100));
        }
        else if (i == 10) { // 综合：大规模随机位置环
            n = 10000; pos = (int)(rng() % 10000);
            for(int j=0; j<n; ++j) vals.push_back((int)(rng() % 200000) - 100000);
        }

        // 补齐 vals (针对未手动赋值的情况)
        if (vals.empty() && n > 0) {
            for(int j=0; j<n; ++j) vals.push_back(j);
        }

        write_test_case(i, n, pos, vals);
        cout << "Generated Case " << i << ": n=" << n << ", pos=" << pos << endl;
    }

    return 0;
}

测试点覆盖说明表

如何配置到 OJ：

1. 编译生成器：g++ gen.cpp -o gen -std=c++14 -O2
2. 运行生成器：./gen
3. 上传数据：将产生的 1.in 到 10.out 共 20 个文件打包上传至你的 OJ 题目后台。

复杂度与规范说明：

• 文件大小：总节点数 $10^4$，包含数值，每个输入文件约 100KB。10 个测试点约 1MB，远低于 2MB 限制。
• 生成时间：全过程瞬间完成（< 0.1s），不存在超时风险。
• 非递归逻辑：生成器和答案判定均为线性循环，不会发生爆栈。
• 异常处理：已处理 $n=0$ 的情况；$pos$ 严格限制在 $[-1, n-1]$ 范围内，不存在除零或数组越界。

在 NOI 竞赛中，处理链表问题时，我们追求的是极致的空间效率和代码的鲁棒性。这道题目从暴力记录地址到最优的快慢指针，体现了算法从“存储”到“计算”的升华。

版本一：哈希集合法（空间换时间）

思路思考： 最直接的办法是记录“我来过哪里”。当我们遍历链表时，将每个节点的地址（注意不是值）存入一个集合。如果当前节点已经存在于集合中，说明我们回到了曾经走过的地方，即存在环。

• 时间复杂度分析：$O(n \log n)$。遍历一遍链表 $O(n)$，每次插入/查找 std::set 耗时 $O(\log n)$。
• 空间复杂度分析：$O(n)$。最坏情况下（无环）需要存入所有节点的指针。
• 评价：逻辑最简单，但在内存限制严格（如 32MB）或数据量极大时可能导致 MLE（内存超限）。

#include <iostream>
#include <vector>
#include <set>

using namespace std;

// 链表节点结构定义
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 辅助函数：根据输入构建带环链表
ListNode* buildList(int n, int pos, const vector<int>& vals) {
    if (n == 0) return nullptr;
    vector<ListNode*> nodes;
    for (int v : vals) nodes.push_back(new ListNode(v));
    
    // 串联链表
    for (int i = 0; i < n - 1; ++i) nodes[i]->next = nodes[i+1];
    
    // 建立环：尾部指向 pos 位置的节点
    if (pos != -1 && pos < n) {
        nodes[n-1]->next = nodes[pos];
    }
    return nodes[0];
}

bool hasCycleHash(ListNode* head) {
    set<ListNode*> visited; // 存储节点指针地址
    ListNode* cur = head;
    while (cur != nullptr) {
        // 关键点：检查当前地址是否出现过
        if (visited.count(cur)) {
            return true;
        }
        visited.insert(cur);
        cur = cur->next;
    }
    return false;
}

int main() {
    int n, pos;
    if (!(cin >> n >> pos)) return 0;
    vector<int> vals(n);
    for (int i = 0; i < n; ++i) cin >> vals[i];

    ListNode* head = buildList(n, pos, vals);

    if (hasCycleHash(head)) cout << "true" << endl;
    else cout << "false" << endl;

    return 0;
}

版本二：最优解 - 快慢指针（Floyd 判环算法）

思路思考： 利用两个指针以不同的速度前进。如果链表有环，快指针最终一定会从后方追上慢指针（套圈）；如果没环，快指针会先到达终点。

• 时间复杂度分析：$O(n)$。
  • 无环：快指针走 $n/2$ 步到终点。
  • 有环：慢指针进入环后，快指针最多在环长步数内追上慢指针。
• 空间复杂度分析：$O(1)$。只使用了两个指针变量，与 $n$ 的大小无关。
• 评价：这是 NOI 竞赛中的标杆解法。

#include <iostream>
#include <vector>

using namespace std;

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

bool hasCycleFastSlow(ListNode* head) {
    // 边界处理：空链表或只有一个节点的链表必无环
    if (head == nullptr || head->next == nullptr) {
        return false;
    }

    ListNode* slow = head;      // 慢指针，每次走 1 步
    ListNode* fast = head;      // 快指针，每次走 2 步

    // 关键点：循环条件必须检查 fast 和 fast->next
    // 因为 fast 跑得快，它会先触碰边界 nullptr
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next; // 易错点：如果 fast->next 为空，这里会崩溃

        // 核心逻辑：一旦相遇，证明有环
        if (slow == fast) {
            return true;
        }
    }

    return false;
}

// 复用版本一的 buildList 和 main...
// 为了完整运行，这里重复部分逻辑
ListNode* buildList(int n, int pos, const vector<int>& vals) {
    if (n == 0) return nullptr;
    vector<ListNode*> nodes;
    for (int v : vals) nodes.push_back(new ListNode(v));
    for (int i = 0; i < n - 1; ++i) nodes[i]->next = nodes[i+1];
    if (pos != -1 && pos < (int)nodes.size()) nodes[n-1]->next = nodes[pos];
    return nodes[0];
}

int main() {
    ios::sync_with_stdio(false); // NOI 常用 IO 优化
    cin.tie(nullptr);

    int n, pos;
    if (!(cin >> n >> pos)) return 0;
    vector<int> vals(n);
    for (int i = 0; i < n; ++i) cin >> vals[i];

    ListNode* head = buildList(n, pos, vals);

    if (hasCycleFastSlow(head)) cout << "true" << endl;
    else cout << "false" << endl;

    return 0;
}

教练的深度分析与优化建议

1. 为什么快指针步长选 2？

• 思考：选 3、4 甚至更大行不行？
• 结论：行，但没必要。快指针步长为 2 时，每次循环与慢指针的相对距离缩小 1。在环中，相对距离为 $D$，经过 $D$ 次操作距离变为 0。如果步长选 3，相对距离缩小 2，若 $D$ 是奇数，快指针可能会“跳过”慢指针，需要更多复杂的证明。2 是最稳健且简单的。

2. 时间复杂度优化建议

• 虽然 $O(n)$ 已是理论最优，但在处理海量数据（如 $10^7$ 个节点）时，内存访问的**局部性（Cache Locality）**会变差。
• 竞赛技巧：在 OI 中，如果不需要动态删除节点，建议使用静态数组模拟链表（即所谓的“静态链表”），用数组下标代替指针。这样节点在内存中是连续的，处理速度比 new 出来的节点快得多。

3. 读题关键词与易错点总结

• 关键词“常量内存”：看到这个词，立马划掉 set 和 map，思考双指针或位运算技巧。
• 易错点：空指针解引用：
  • 在写 fast->next->next 时，脑子里必须立刻跳出：“如果 fast->next 是空的怎么办？”
  • NOI 教练秘籍：养成写 while(fast && fast->next) 的习惯，这能保住你 10 到 20 分的边界测试分。

4. 空间思考

• 版本二的 $O(1)$ 空间是指“辅助空间”。实际上存储链表本身依然需要 $O(n)$。但在判环逻辑中，我们没有申请任何与 $n$ 规模相关的容器。

总结：在处理链表环问题时，双指针法不仅是面试的宠儿，更是竞赛中处理复杂图论找环（如基环树）的基础思想。务必烂熟于心！