你好！我是你的 OI 教练。今天我们要攻克的是链表操作中的一个经典问题：分隔链表（Partition List）。

在 NOI 竞赛中，链表题目不仅考察你对指针的熟练度，更考察你对 稳定性（Stability） 的维护能力——即在重组数据时，不改变相同性质元素之间的相对先后顺序。

一、 预备知识点 checklist

1. 链表结构体定义：熟练掌握 struct 封装 val 与 next 指针。
2. 虚拟头节点（Dummy Node）技巧：这是处理链表题目最核心的技巧，能帮你完美避开“对空头节点解引用”的致命错误。
3. 多链表拆分与合并：理解如何将一个物理链表逻辑上拆分为两个，再重新首尾相连。
4. 指针稳定性：在移动节点时，确保不打乱原有的逻辑顺序。

二、 题目描述：分隔链表 (Partition List)

题目背景： 在某些排序算法（如快速排序）的底层实现中，我们需要根据一个基准值 $x$ 将序列分为两部分。本题要求在链表上实现这一操作，并保持每一部分的相对顺序不变。

题目要求： 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你应当 保留 两个分区中每个节点的初始相对位置。

输入格式 (Standard Input)：

• 第一行包含两个整数 $n$ 和 $x$，分别表示链表的长度和基准值。
• 第二行包含 $n$ 个整数，表示链表各节点的值。

输出格式 (Standard Output)：

• 输出一行，包含 $n$ 个整数，表示分隔后的链表元素，元素之间以空格分隔。

输入样例 1：

6 3
1 4 3 2 5 2

输出样例 1：

1 2 2 4 3 5

输入样例 2：

2 2
2 1

输出样例 2：

1 2

数据规模与约定：

• $0 \le n \le 200$
• $-100 \le \text{节点值} \le 100$
• $-200 \le x \le 200$
• 时间限制：1.0s
• 内存限制：128MB

三、 教练的草稿纸：启发式推理过程

当我们面对要把一个链表“按属性拆开”的需求时，最直观且稳妥的办法不是在原链表上通过复杂的交换逻辑来实现，而是**“化整为零，重新组装”**。

1. 策略选择：创建两条“生产线”

请在草稿纸上画出两条并行的空白链表：

• Small 生产线：专门收集所有值 小于 $x$ 的节点。
• Large 生产线：专门收集所有值 大于等于 $x$ 的节点。

2. 模拟过程

拿样例 1 举例 ($x=3$)：1 -> 4 -> 3 -> 2 -> 5 -> 2

1. 碰到 1：小于 3，挂到 Small 线。 Small: 1
2. 碰到 4：大于等于 3，挂到 Large 线。 Large: 4
3. 碰到 3：大于等于 3，挂到 Large 线。 Large: 4 -> 3
4. 碰到 2：小于 3，挂到 Small 线。 Small: 1 -> 2
5. ...以此类推。

3. 关键的收尾步骤

• 合并：将 Small 线的末尾指向 Large 线的开头（跳过 Large 的虚拟头）。
• 断后（易错点）：Large 线的最后一个节点的 next 必须设为 nullptr。如果不做这一步，链表可能会形成环，导致死循环！

四、 算法流程图 (Mermaid 风格)

为了符合 NOI 规范，我们使用两个虚拟头节点来实现：

graph TD
    Start("开始处理") --> Init("创建两个Dummy节点: SmallHead 和 LargeHead")
    Init --> Pointers("设置两个指针: S_Tail 指向 SmallHead, L_Tail 指向 LargeHead")
    Pointers --> Loop{"遍历原链表 Curr 是否为空?"}
    
    Loop -- "否" --> Check{"当前节点值是否小于 X?"}
    Check -- "是" --> AttachSmall("S_Tail 的 Next 指向当前节点")
    AttachSmall --> MoveSmall("S_Tail 后移一步")
    
    Check -- "否" --> AttachLarge("L_Tail 的 Next 指向当前节点")
    AttachLarge --> MoveLarge("L_Tail 后移一步")
    
    MoveSmall --> NextNode("Curr 指向原链表的下一个节点")
    MoveLarge --> NextNode
    NextNode --> Loop
    
    Loop -- "是" --> Finalize("将 L_Tail 的 Next 设为空指针")
    Finalize --> Combine("将 S_Tail 的 Next 指向 LargeHead 的下一个节点")
    Combine --> Return("返回 SmallHead 的下一个节点作为新头")
    Return --> End("结束")

五、 复杂度分析思考过程

• 时间复杂度：

  • 我们只需要从头到尾扫描一遍原链表。
  • 在每个节点上的操作（判断、指针赋值）都是常数级别的。
  • 分析结果：$O(n)$。

• 空间复杂度：

  • 思考点：我们有没有创建新的节点？
  • 结论：没有，我们只是修改了原有节点的 next 指针。虽然创建了两个 Dummy 节点和若干辅助指针，但它们的数量是常数。
  • 分析结果：$O(1)$ （不计入存储原始数据的空间）。

• 时间复杂度优化建议：

  • 对于 $n \le 200$ 的数据，此 $O(n)$ 算法已经达到理论最优，耗时基本可以忽略不计。在 NOI 实际比赛中，如果 $n$ 增加到 $10^6$，此算法依然稳健。

六、 读题关键词与坑点总结

1. “保留相对位置”：

   • 这是最重要的关键词。它意味着你不能直接使用类似快速排序的“头尾双指针交换法”，因为那样会破坏稳定性。
   • 对策：必须使用“尾插法”构建两条子链表。

2. “大于或等于”：

   • 看清分界线的包含关系。本题中 $x$ 属于右半部分。

3. 内存安全（链表封底）：

   • 关键词在哪？：虽然题目没直接说，但“重新拼接”暗示了风险。
   • 坑点：如果原链表的最后一个节点被分到了 Small 生产线，而倒数第二个节点（其 next 本来指向最后一个节点）被分到了 Large 生产线，那么 Large 生产线的末尾依然牵连着 Small 线里的节点。
   • 对策：务必记得 large_tail->next = nullptr;。

4. $n=0$ 的处理：

   • 读题时注意范围。如果输入为空，Dummy 节点的方法依然有效，能保证不崩溃。