链表分割算法实战：以指定值划分节点顺序

问题背景

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

核心思路

为了在 O(n) 时间复杂度和 O(1) 空间复杂度内完成操作，我们可以采用'双链表拼接'的策略。与其在原链表上原地修改指针（容易出错且破坏结构），不如创建两个新的虚拟头节点（Sentinel Nodes）：guardLess 和 guardGreater。

遍历原链表时，根据节点值与 x 的大小关系，分别尾插到这两个新链表中。这样天然保证了相对顺序不变。最后将两个链表首尾相连，并断开多余指针即可。

具体实现时，我们初始化两个哨兵节点，以及对应的尾指针 lessTail 和 greaterTail。使用游标 curNode 遍历原链表，若当前节点值小于 x，将其接在 lessTail 后，并更新 lessTail；否则接在 greaterTail 后。遍历结束后，连接 lessTail->next 指向 guardGreater->next，务必将 greaterTail->next 置为 nullptr，防止形成环。最后返回 guardLess->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;
        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 = ;

        
        pHead = guardLess->next;

        
         guardGreater;
         guardLess;

         pHead;
    }
};