为了方便你快速创建 OJ 测试数据，我编写了这个完整的数据生成器。它能够生成 10 组符合 NOI 规范的 .in 和 .out 文件。

数据生成器设计重点

1. 逻辑一致性：根据 LeetCode 的题目要求，如果链表相交，则从相交点开始，后续的所有节点值必须完全一致。
2. 区分“值”与“地址”：在测试点 8 中，我特意设计了“两个链表节点值完全相同但不相交”的情况，用来拦截那些只判断 val 而不判断指针地址的错误算法。
3. 规模控制：最大数据量 $N, M = 3 \times 10^4$，生成的 20 个文件总大小约 1.5MB，单文件远小于 2MB。
4. 鲁棒性：采用迭代方式生成，不使用递归，保证在大规模数据下不会爆栈。

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

using namespace std;

// 使用 mt19937 生成高质量随机数
mt19937 rng(20251230);

/**
 * @brief 生成一组测试数据并写入文件
 * @param id 测试点编号
 * @param n 链表 A 的长度
 * @param m 链表 B 的长度
 * @param skipA A 中跳过的节点数
 * @param skipB B 中跳过的节点数
 * @param intersect 是否相交
 */
void make_case(int id, int n, int m, int skipA, int skipB, bool intersect) {
    string in_name = to_string(id) + ".in";
    string out_name = to_string(id) + ".out";

    vector<long long> listA(n), listB(m);
    long long intersectVal = 0;

    // 1. 生成公共部分或独立部分
    if (intersect) {
        // 确定公共部分长度
        int commonLen = n - skipA; 
        // 生成公共节点值
        vector<long long> commonPart(commonLen);
        for (int i = 0; i < commonLen; ++i) 
            commonPart[i] = (long long)(rng() % 2000000001) - 1000000000;
        
        intersectVal = commonPart[0];

        // 填充 A 的前缀
        for (int i = 0; i < skipA; ++i) 
            listA[i] = (long long)(rng() % 2000000001) - 1000000000;
        // 填充 A 的公共部
        for (int i = 0; i < commonLen; ++i) 
            listA[skipA + i] = commonPart[i];

        // 填充 B 的前缀
        for (int i = 0; i < skipB; ++i) 
            listB[i] = (long long)(rng() % 2000000001) - 1000000000;
        // 填充 B 的公共部（必须与 A 一致）
        for (int i = 0; i < commonLen; ++i) 
            listB[skipB + i] = commonPart[i];
    } else {
        intersectVal = 0;
        skipA = n; skipB = m;
        for (int i = 0; i < n; ++i) listA[i] = (long long)(rng() % 100000);
        for (int i = 0; i < m; ++i) listB[i] = (long long)(rng() % 100000) + 200000; // 保证不重叠
    }

    // 2. 写入 .in 文件
    ofstream fin(in_name);
    fin << intersectVal << " " << n << " " << m << " " << skipA << " " << skipB << "\n";
    for (int i = 0; i < n; ++i) fin << listA[i] << (i == n - 1 ? "" : " ");
    fin << "\n";
    for (int i = 0; i < m; ++i) fin << listB[i] << (i == m - 1 ? "" : " ");
    fin << endl;
    fin.close();

    // 3. 写入 .out 文件
    ofstream fout(out_name);
    if (intersect && n > 0 && m > 0 && skipA < n && skipB < m) {
        fout << "Intersected at " << intersectVal << endl;
    } else {
        fout << "No intersection" << endl;
    }
    fout.close();
}

int main() {
    // 测试点 1: 边界 - 其中一个链表为空
    make_case(1, 0, 5, 0, 5, false);
    
    // 测试点 2: 边界 - 不相交
    make_case(2, 3, 2, 3, 2, false);

    // 测试点 3: 场景 - 在第一个节点相交 (skip=0)
    make_case(3, 5, 5, 0, 0, true);

    // 测试点 4: 场景 - 在最后一个节点相交
    make_case(4, 10, 10, 9, 9, true);

    // 测试点 5: 场景 - A 很长, B 很短, 相交在末尾
    make_case(5, 1000, 10, 995, 5, true);

    // 测试点 6: 场景 - B 很长, A 很短, 相交在末尾
    make_case(6, 10, 1000, 5, 995, true);

    // 测试点 7: 典型 - 中等规模常规相交
    make_case(7, 5000, 4000, 2000, 1000, true);

    // 测试点 8: 陷阱 - 节点值完全相同但不相交 (考察地址判定)
    {
        ofstream fin("8.in");
        fin << "0 5 5 5 5\n1 1 1 1 1\n1 1 1 1 1\n"; fin.close();
        ofstream fout("8.out");
        fout << "No intersection\n"; fout.close();
    }

    // 测试点 9: 压力 - 大规模随机相交 (3 * 10^4)
    make_case(9, 30000, 30000, 15000, 15000, true);

    // 测试点 10: 压力 - 极大负数值相交
    make_case(10, 30000, 25000, 10000, 5000, true);

    cout << "All 10 test cases generated successfully." << endl;
    return 0;
}

数据测试点分布说明表

给 OJ 管理者的部署建议：

1. 编译与运行：直接使用 g++ gen.cpp -o gen -std=c++14 编译并运行，即可在当前目录获得 20 个文件。
2. 文件大小：由于 $N, M$ 只有 3 万，且节点值为整数，单文件大小控制在 200KB-500KB 之间，总包大小约 1.5MB，上传非常方便。
3. 时间限制建议：建议设为 1.0s。$O(N+M)$ 解法实际运行时间通常在 0.01s 左右，但 1.0s 可以给带常数的解法和不同环境留足空间。
4. 空间限制建议：建议设为 128MB。$O(1)$ 算法仅需几百 KB，但 128MB 可以允许学生使用 std::set 这种 $O(N)$ 空间的解法通过。

在 NOI 竞赛中，链表题目不仅仅考察数据结构，更考察对**地址（指针）**的底层理解。下面我将为你展示从暴力到最优的三个版本。

数据构造逻辑（竞赛通用）

为了让代码可运行，我们需要先根据输入格式构造两个真实的相交链表。

版本一：暴力双重循环 ($O(N \times M)$)

思路思考： 最直观的想法是：对于链表 A 中的每一个节点，都去链表 B 中排查一遍，看是否存在地址完全相同的节点。

• 时间复杂度：$O(N \times M)$。对于本题 $3 \times 10^4$ 的规模，最坏情况需要 $9 \times 10^8$ 次运算，在 1.0s 内极大概率 TLE。
• 空间复杂度：$O(1)$。

#include <iostream>
#include <vector>

using namespace std;

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

// 暴力判别函数
ListNode *getIntersectionNodeBrute(ListNode *headA, ListNode *headB) {
    ListNode *pA = headA;
    while (pA != nullptr) {
        ListNode *pB = headB;
        while (pB != nullptr) {
            // 关键点：比较的是指针地址，而不是 pA->val == pB->val
            if (pA == pB) return pA;
            pB = pB->next;
        }
        pA = pA->next;
    }
    return nullptr;
}

// 模拟构造和主函数省略，见下文最优解版本

版本二：哈希表/地址记录法 ($O(N + M)$)

思路思考： 我们可以通过“记账”来优化。先遍历一次链表 A，把所有节点的地址存入一个 std::set。然后再遍历链表 B，检查当前节点地址是否在账本中。

• 时间复杂度：$O(N \log N + M \log N)$。
• 空间复杂度：$O(N)$。需要额外空间存储 A 的所有指针。
• 评价：在 NOI 竞赛中，若空间限制为 128MB，此法可行，但如果限制为 16MB 则会 MLE。

#include <set>
ListNode *getIntersectionNodeHash(ListNode *headA, ListNode *headB) {
    set<ListNode*> addr_set;
    ListNode *cur = headA;
    while (cur) {
        addr_set.insert(cur);
        cur = cur->next;
    }
    cur = headB;
    while (cur) {
        if (addr_set.count(cur)) return cur;
        cur = cur->next;
    }
    return nullptr;
}

版本三：最优解 - 浪漫相遇法 ($O(N + M)$ 时间, $O(1)$ 空间)

思路思考： 利用“交换人生”的思路。pA 走完 A 就去走 B，pB 走完 B 就去走 A。由于总路程 $L_1 + L_2$ 是相等的，他们会在相交点准时碰撞。

• 时间复杂度：$O(N + M)$。每个指针最多走两遍全程。
• 空间复杂度：$O(1)$。

#include <iostream>
#include <vector>

using namespace std;

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

// 最优解核心算法
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if (!headA || !headB) return nullptr;
    
    ListNode *pA = headA;
    ListNode *pB = headB;

    // 关键点：如果相交，会在交点相遇；如果不相交，最终会同时变为 nullptr (nullptr == nullptr 成立)
    while (pA != pB) {
        // 易错点：必须在 pA 彻底为 nullptr 后再转向，不能在 pA->next == nullptr 时转向
        pA = (pA == nullptr) ? headB : pA->next;
        pB = (pB == nullptr) ? headA : pB->next;
    }
    return pA;
}

int main() {
    // 1. 读取构造参数
    long long intersectVal;
    int n, m, skipA, skipB;
    if (!(cin >> intersectVal >> n >> m >> skipA >> skipB)) return 0;

    vector<long long> valsA(n), valsB(m);
    for (int i = 0; i < n; ++i) cin >> valsA[i];
    for (int i = 0; i < m; ++i) cin >> valsB[i];

    // 2. 构造链表 A 和 B
    // 构造公共部分
    ListNode *common = nullptr, *tail = nullptr;
    vector<ListNode*> nodesA, nodesB;

    // 先构造 A 的前缀
    for (int i = 0; i < skipA; ++i) nodesA.push_back(new ListNode(valsA[i]));
    
    // 构造公共部分并接入 A
    for (int i = skipA; i < n; ++i) {
        ListNode *newNode = new ListNode(valsA[i]);
        if (!common) common = newNode;
        nodesA.push_back(newNode);
    }
    // 连成链表 A
    for (int i = 0; i < n - 1; ++i) nodesA[i]->next = nodesA[i+1];

    // 构造 B 的前缀
    for (int i = 0; i < skipB; ++i) nodesB.push_back(new ListNode(valsB[i]));
    
    // 关键点：将 B 的前缀最后一个节点连向 A 的公共起始点
    if (m > 0) {
        if (skipB > 0) {
            for (int i = 0; i < skipB - 1; ++i) nodesB[i]->next = nodesB[i+1];
            // 真正实现“相交”：B 的前缀末尾指向 A 链表中的某个已有节点
            nodesB[skipB - 1]->next = (skipA < n) ? nodesA[skipA] : nullptr;
        }
    }

    ListNode *headA = (n > 0) ? nodesA[0] : nullptr;
    ListNode *headB = (m > 0) ? (skipB > 0 ? nodesB[0] : (skipA < n ? nodesA[skipA] : nullptr)) : nullptr;

    // 3. 执行算法
    ListNode *result = getIntersectionNode(headA, headB);

    // 4. 输出
    if (result) cout << "Intersected at " << result->val << endl;
    else cout << "No intersection" << endl;

    return 0;
}

时间复杂度优化建议（NOI 进阶）

1. 长度差对齐法： 这是另一种 $O(1)$ 空间的经典解法。先计算 A 和 B 的长度 $lenA, lenB$，算出差值 $D = |lenA - lenB|$。让长的先走 $D$ 步，然后两个同步走。

   • 优化点：这种方法在某些特定环境下比“交换人生”法少走一些无效路程，且逻辑更直观，不容易在循环边界出错。

2. IO 性能： 如果 $N, M$ 达到 $10^6$，cin 的效率将无法忍受。务必使用 scanf 或快读：

   inline int read() {
       int x=0; char ch=getchar();
       while(ch<'0'||ch>'9') ch=getchar();
       while(ch>='0'&&ch<='9') x=x*10+ch-'0', ch=getchar();
       return x;
   }
   

关键点与易错点总结

• 节点 vs 数值：读题时，看到“相交”二字，脑子里第一反应必须是**“指针地址 p1 == p2”**，而绝对不是 p1->val == p2->val。
• 空指针处理：while(pA != pB) 这种写法非常优雅，因为它自动处理了不相交的情况（最终 pA 和 pB 都会变成 nullptr，满足退出条件）。
• 死循环风险：如果两个链表不相交且长度相等，pA 和 pB 会同时到达 nullptr 并退出。如果长度不等，它们各走一遍对方后也会同时到达 nullptr。关键是必须处理 nullptr 转向。

读题关键词

• “相交” $\to$ 指针地址相同。
• “$O(1)$ 内存” $\to$ 不能用 set、map、数组记录路径。
• “不修改链表结构” $\to$ 不能临时断开或反转链表。