为了方便你直接在 Linux 或 Windows 环境下生成测试数据，我为你编写了一个完整的数据生成器。它包含了标准算法逻辑（用于产生 .out 文件）和针对不同边界条件的生成逻辑。

数据生成器设计逻辑

1. 覆盖性：从空链表到最大规模，从全小于 $x$ 到全大于 $x$，以及各种穿插、重复、倒序情况。
2. 稳定性：使用 std::vector 模拟链表逻辑来生成答案，避免在生成器中频繁 new/delete。
3. 安全性：固定随机数种子 mt19937，保证数据可复现。
4. 规范性：严格遵循 NOI 的 1.in/1.out 文件命名规范。

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

using namespace std;

/**
 * @brief 标准答案逻辑 (用于生成 .out 文件)
 * 采用 vector 模拟，确保不爆栈且逻辑清晰
 */
vector<int> get_standard_answer(int n, int x, const vector<int>& nums) {
    if (n == 0) return {};
    vector<int> small, large;
    for (int v : nums) {
        if (v < x) small.push_back(v);
        else large.push_back(v);
    }
    // 拼接两部分
    vector<int> res = small;
    res.insert(res.end(), large.begin(), large.end());
    return res;
}

/**
 * @brief 数据写入函数
 */
void make_test_case(int id, int n, int x, const vector<int>& nums) {
    string in_file = to_string(id) + ".in";
    string out_file = to_string(id) + ".out";

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

    // 写入 .out 文件
    ofstream fout(out_file);
    vector<int> res = get_standard_answer(n, x, nums);
    for (int i = 0; i < (int)res.size(); ++i) {
        fout << res[i] << (i == (int)res.size() - 1 ? "" : " ");
    }
    if (n > 0) fout << endl; // 非空数据输出换行
    fout.close();
}

int main() {
    mt19937 rng(20251230); // 固定种子

    for (int i = 1; i <= 10; ++i) {
        int n = 0, x = 0;
        vector<int> nums;

        switch (i) {
            case 1: // 边界：空链表
                n = 0; x = 10;
                break;
            case 2: // 边界：只有一个元素，且 < x
                n = 1; x = 50;
                nums = {20};
                break;
            case 3: // 边界：只有一个元素，且 >= x
                n = 1; x = 50;
                nums = {70};
                break;
            case 4: // 情况：所有元素都 < x
                n = 20; x = 100;
                for(int j=0; j<n; ++j) nums.push_back((int)(rng() % 50));
                break;
            case 5: // 情况：所有元素都 >= x
                n = 20; x = 0;
                for(int j=0; j<n; ++j) nums.push_back((int)(rng() % 50) + 1);
                break;
            case 6: // 情况：已经分好序的链表 (1 2 3 | 4 5 6)
                n = 50; x = 25;
                for(int j=0; j<n; ++j) nums.push_back(j);
                break;
            case 7: // 情况：完全倒序的分隔 (4 5 6 | 1 2 3)
                n = 50; x = 25;
                for(int j=49; j>=0; --j) nums.push_back(j);
                break;
            case 8: // 情况：大量重复元素，且等于 x
                n = 100; x = 10;
                for(int j=0; j<n; ++j) nums.push_back(10);
                break;
            case 9: // 情况：随机分布，中等规模
                n = 150; x = (int)(rng() % 100) - 50;
                for(int j=0; j<n; ++j) nums.push_back((int)(rng() % 201) - 100);
                break;
            case 10: // 情况：最大规模，极端值插空
                n = 200; x = 0;
                for(int j=0; j<n; ++j) {
                    if(j % 2 == 0) nums.push_back((int)(rng() % 100) + 1); // Large
                    else nums.push_back((int)(rng() % 100) - 100);       // Small
                }
                break;
        }

        make_test_case(i, n, x, nums);
        cout << "Test Case " << i << " generated. (n=" << n << ")" << endl;
    }

    return 0;
}

测试点详细分布说明

如何配置到 OJ：

1. 编译生成器：g++ gen.cpp -o gen -std=c++14 -O2
2. 运行生成器：./gen (Linux) 或 gen.exe (Windows)。
3. 上传数据：将产生的 1.in 到 10.out 共 20 个文件压缩上传。

性能与安全保证：

• 文件大小：由于 $n \le 200$，每个文件仅几百字节，总大小远低于 2MB。
• 时间开销：生成所有数据的时间在 10ms 左右。
• 内存安全：不涉及深度递归，答案生成逻辑采用 std::vector 的顺序遍历，不会出现爆栈或死循环。
• 逻辑鲁棒：在 get_standard_answer 中通过物理分离两个 vector 再合并，模拟了题目的逻辑要求，保证了产出数据的正确性。

作为教练，我会带你从最符合直觉的“容器法”开始，逐步进化到竞赛中最核心的“双指针原地操作”。

链表题目的核心难点在于指针的断开与重连。在草稿纸上模拟时，一定要画出每个指针的变化。

版本一：辅助容器法（最稳妥的暴力思路）

思路思考： 既然链表操作容易出错，我们先用最简单的方法：用两个数组（或 std::vector）分别存储“小于 $x$”和“大于等于 $x$”的节点值，然后重新按顺序输出或构造链表。

• 时间复杂度分析：$O(n)$，只需遍历一次原数据。
• 空间复杂度分析：$O(n)$，使用了两个额外的 vector 存储所有数据。
• 适用场景：在竞赛中，如果 $n$ 较小且内存充裕，这是最不容易写挂（出错）的方法。

#include <iostream>
#include <vector>

using namespace std;

// NOI 风格：手写链表节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

int main() {
    int n, x;
    if (!(cin >> n >> x)) return 0;

    vector<int> small, large;
    for (int i = 0; i < n; ++i) {
        int v; cin >> v;
        if (v < x) small.push_back(v);
        else large.push_back(v);
    }

    // 重新组合输出
    bool first = true;
    for (int v : small) {
        if (!first) cout << " ";
        cout << v;
        first = false;
    }
    for (int v : large) {
        if (!first) cout << " ";
        cout << v;
        first = false;
    }
    cout << endl;

    return 0;
}

版本二：原地迭代双链表法（最优复杂度解法）

思路思考： 在 NOI 竞赛中，如果题目明确要求“在原链表上操作”或者空间限制极严，我们就需要原地修改指针。 我们可以维护两个逻辑上的“半成品链表”，一个接小的，一个接大的。

• 时间复杂度分析：$O(n)$，每个节点只被处理一次。
• 空间复杂度分析：$O(1)$，除了两个 dummy 哨兵节点外，没有使用额外空间。

关键点/易错点注释：

1. 哨兵节点 (Dummy Node)：使用 smallHead 和 largeHead 可以避免处理“第一个节点是谁”的边界问题。
2. 尾指针 (Tail Pointer)：维护 smallTail 和 largeTail 始终指向当前子链表的末尾。
3. 封底操作：这是最容易漏掉的一步，largeTail->next = nullptr 必须做，否则新链表的末尾可能还连着旧节点，形成环。

#include <iostream>

using namespace std;

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

int main() {
    int n, x;
    if (!(cin >> n >> x)) return 0;

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

    // --- 核心算法开始 ---
    // 1. 创建两个哨兵节点，简化头部逻辑
    ListNode* smallHead = new ListNode(0);
    ListNode* largeHead = new ListNode(0);
    
    // 2. 维护两个子链表的尾指针
    ListNode* smallTail = smallHead;
    ListNode* largeTail = largeHead;

    // 3. 遍历原链表进行拆分
    ListNode* p = head;
    while (p != nullptr) {
        if (p->val < x) {
            smallTail->next = p;    // 接入小链表
            smallTail = p;          // 尾指针后移
        } else {
            largeTail->next = p;    // 接入大链表
            largeTail = p;          // 尾指针后移
        }
        p = p->next;
    }

    // 4. 关键点：大链表末尾封底，防止链表成环
    largeTail->next = nullptr; 

    // 5. 拼接两个链表
    smallTail->next = largeHead->next;

    // 6. 确定最终结果的头节点
    ListNode* result = smallHead->next;
    // --- 核心算法结束 ---

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

    // 竞赛习惯：手动释放内存
    // 注意：这里为了简洁未写全释放逻辑，实际工程需 delete 所有节点
    return 0;
}

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

1. 时间复杂度优化建议

对于这道题，$O(n)$ 已经是理论极限。在 NOI 竞赛中，如果 $n$ 达到了 $10^6$ 级别，需要注意：

• IO 优化：使用 scanf/printf 或 cin.tie(0)->sync_with_stdio(0)。
• 内存池优化：链表节点的 new 操作其实很慢。如果节点数极多，建议使用静态数组模拟链表：

  int val[MAXN], nxt[MAXN], tot;
  // 这样分配节点只需要 tot++，速度远快于 new
  

2. 空间复杂度思考

• 版本一的空间是 $O(n)$，因为我们存了所有的值。
• 版本二的空间是 $O(1)$，我们仅仅是重排了节点之间的“线”（指针）。

3. 为什么必须 largeTail->next = nullptr？

想象原链表是 1 -> 4 -> 2，$x=3$。

1. p 指向 1：smallTail 接上 1。
2. p 指向 4：largeTail 接上 4。注意此时 4 的 next 依然指向 2。
3. p 指向 2：smallTail 接上 2。此时 smallTail 是 2。
4. 拼接：2 连上 4。
5. 结果：1 -> 2 -> 4 -> 2 ... 形成死循环。所以必须在最后强制把 4 的 next 斩断。

4. 读题关键词总结

• “保留初始相对位置”：看到这个词，立刻划掉“交换法”，改用“双队列/双子链表法”。
• “分隔”：暗示了 $O(n)$ 的线性扫描逻辑。
• “小于 x” 和 “大于或等于 x”：注意 = 的位置，防止逻辑判断写错导致节点分错组。