链表分割：以指定值 x 为基准划分链表

问题描述

给定一个链表的头指针 pHead 和一个整数值 x，要求将链表分割成两部分。所有小于 x 的结点排在大于或等于 x 的结点之前，且不能改变原来数据的相对顺序。返回分割后的新链表的头指针。

核心要求：

• 时间复杂度为 O(n)
• 空间复杂度为 O(1)

思路分析

这道题的核心在于如何高效地重组链表而不破坏原有顺序。如果直接原地修改指针，逻辑会非常复杂，容易出错。比较稳妥的做法是构建两条新的子链表：一条存放小于 x 的节点，另一条存放大于等于 x 的节点。

为了简化边界处理（比如空链表、第一个节点就满足条件等），我们引入两个哨兵节点（Dummy Node）作为虚拟头结点。这样在尾插操作时，无需判断当前是否为头节点，统一由哨兵位接管。

具体步骤如下：

1. 初始化：创建 guardLess 和 guardGreater 两个哨兵节点，分别对应两条子链表的头部。同时维护两个尾指针 lessTail 和 greaterTail，初始指向各自的哨兵节点。
2. 遍历：使用移动指针 curNode 扫描原链表。根据节点值与 x 的比较结果，将节点尾插到对应的子链表中，并更新相应的尾指针。
3. 连接：遍历结束后，将 lessTail->next 指向 guardGreater->next，完成两条链表的拼接。
4. 收尾：务必将新链表的最后一个节点（即 greaterTail）的 next 置为 nullptr，防止形成环。最后释放哨兵节点内存，返回 guardLess->next 作为新头指针。

代码实现

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        if (pHead == nullptr) return nullptr;

        // 创建哨兵节点，避免处理头指针为空的情况
        ListNode* guardLess = new ListNode(-1);
        ListNode* guardGreater = new ListNode(-1);

        // 维护两个子链表的尾指针
        ListNode* lessTail = guardLess;
        ListNode* greaterTail = guardGreater;

        ListNode* curNode = pHead;
        while (curNode) {
            if (curNode->val < x) {
                lessTail->next = curNode;
                lessTail = lessTail->next;
            } else {
                greaterTail->next = curNode;
                greaterTail = greaterTail->next;
            }
            curNode = curNode->next;
        }

        // 连接两个链表
        lessTail->next = guardGreater->next;

        // 断开尾部，防止链表带环
        greaterTail->next = nullptr;

        // 保存新链表的头结点
        pHead = guardLess->next;

        // 释放手动开辟的哨兵位头结点
        delete guardGreater;
        delete guardLess;

        return pHead;
    }
};

细节说明

在实际编写时，有几个关键点需要特别注意：

1. 哨兵位的作用：它让插入逻辑变得统一，不需要单独判断'这是不是第一个节点'。
2. 断环操作：很多初学者容易忘记 greaterTail->next = nullptr。如果不执行这一步，当原链表最后一个节点被挂到 greater 链表后，它的 next 可能还指向后续节点（虽然遍历结束了，但指针没清），或者如果原链表本身有环，这里必须显式切断以确保安全。
3. 内存管理：哨兵节点是我们 new 出来的，记得在函数结束前 delete，避免内存泄漏。

这个方案只需要遍历一次链表，逻辑清晰且效率最优，是处理此类链表分区问题的标准解法。