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

链表分割算法详解

问题描述

给定一个链表的头指针 pHead，以及一个整数值 x。要求将链表分割成两部分，使得所有小于 x 的节点排在大于或等于 x 的节点之前。分割后需保持原数据的相对顺序不变，并返回新链表的头指针。

约束条件：

• 时间复杂度：O(n)
• 空间复杂度：O(1)
• 不能改变原有节点的相对顺序

思路分析

要实现原地分割且保持顺序，直接修改节点指针是最优解。核心思路是利用两个哨兵节点（Dummy Node）分别构建两条临时链表：一条存放小于 x 的节点，另一条存放大于等于 x 的节点。

具体步骤如下：

1. 初始化哨兵位：创建 guardLess 和 guardGreater 两个虚拟头结点，避免处理空指针边界情况。
2. 维护尾指针：分别记录两条临时链表的尾部 lessTail 和 greaterTail，这样在插入新节点时可以直接通过尾插法完成，无需遍历查找末尾。
3. 遍历原链表：使用移动指针 curNode 扫描原链表。根据节点值与 x 的比较结果，将其尾插到对应的临时链表中。
4. 连接链表：遍历结束后，将 lessTail 指向 guardGreater 的下一个节点，实现两段链表的拼接。
5. 收尾工作：务必将新链表的最后一个节点 next 置为 nullptr，防止形成环；最后释放哨兵节点占用的内存。

注意：实际编写时，记得断开 greaterTail->next，否则如果原链表后续还有数据，可能会造成逻辑混乱或死循环。

代码实现

以下是基于 C++ 的标准实现，注重指针操作的准确性与内存安全。

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;

         (curNode) {
             (curNode->val < x) {
                
                lessTail->next = curNode;
                lessTail = lessTail->next;
            }  {
                
                greaterTail->next = curNode;
                greaterTail = greaterTail->next;
            }
            
            curNode = curNode->next;
        }

        
        lessTail->next = guardGreater->next;

        
        greaterTail->next = ;

        
        ListNode* result = guardLess->next;

        
         guardLess;
         guardGreater;

         result;
    }
};