分隔链表算法详解：双虚拟头节点拆解合并法
题目解析
给定一个单链表和一个数值 x，需要将链表划分为两个部分：所有小于 x 的节点排在链表前半部分，所有大于或等于 x 的节点排在链表后半部分。
划分后无需改变原链表中节点的相对顺序。例如，若链表为 1→4→3→2→5→2，给定 x=3，则分隔后的链表应为 1→2→2→4→3→5。
解题关键在于不额外开辟大量空间，仅通过指针操作完成节点的重新拼接，时间复杂度需控制在 O(n)，空间复杂度为 O(1)。
算法原理：双虚拟头节点的巧思
单链表的痛点在于头节点可能被修改，且对空链表、单节点链表的处理需要额外的边界判断。虚拟头节点（哑节点） 是解决这类问题的常用手段，它是一个不存储实际值的节点，指向真正的头节点，能让指针操作统一化，无需单独处理边界情况。
核心思路如下：
- 定义两个虚拟头节点，分别对应小值链表和大值链表；
- 定义两个尾指针，分别指向两个链表的末尾，用于快速拼接新节点；
- 遍历原链表，根据节点值的大小，将节点依次拼接到对应链表的末尾；
- 遍历完成后，将小值链表的尾节点指向大值链表的真实头节点，完成合并；
- 返回小值链表的真实头节点。
执行流程图解
以链表 1→4→3→2→5→2、x=3 为例，我们直观看一下拆分与合并的过程。
初始化阶段
- 小值链表虚拟头节点：
dummySmall，尾指针pSmall（初始指向dummySmall） - 大值链表虚拟头节点：
dummyLarge，尾指针pLarge（初始指向dummyLarge） - 遍历指针
p（初始指向原链表头节点）
遍历拆分
遍历过程中，我们需要先保存当前节点的下一个位置，防止断链。然后根据值的大小决定归属：
- 节点
1：小于 3，拼接到小值链表，pSmall后移； - 节点
4：大于 3，拼接到大值链表，pLarge后移； - 节点
3：等于 3，拼接到大值链表，pLarge后移； - 节点
2：小于 3，拼接到小值链表，pSmall后移； - 节点
5：大于 3，拼接到大值链表，pLarge后移； - 节点
2：小于 3，拼接到小值链表，pSmall后移。
此时，小值链表包含 1→2→2，大值链表包含 4→3→5。
合并与收尾
将小值链表尾指针 pSmall 的 next 指向大值链表的真实头节点 dummyLarge->next。同时，务必将大值链表尾节点的 next 置为 null，避免形成环。
最终结果即为 dummySmall->next 指向的完整链表。
C++ 代码实现
结合上述逻辑，下面是完整的 C++ 实现。代码中保留了必要的内存管理细节，符合工程实践习惯。
{
val;
ListNode *next;
() : (), () {}
( x) : (x), () {}
( x, ListNode *next) : (x), (next) {}
};
{
ListNode* dummySmall = ();
ListNode* dummyLarge = ();
ListNode* pSmall = dummySmall;
ListNode* pLarge = dummyLarge;
ListNode* p = head;
(p != ) {
ListNode* temp = p->next;
(p->val < x) {
pSmall->next = p;
pSmall = pSmall->next;
} {
pLarge->next = p;
pLarge = pLarge->next;
}
p->next = ;
p = temp;
}
pSmall->next = dummyLarge->next;
ListNode* res = dummySmall->next;
dummySmall;
dummyLarge;
res;
}
