如何按给定值分隔链表并保持相对顺序？

简化版

分隔链表通常用两个 dummy：一个收集小于 x 的节点，一个收集大于等于 x 的节点。遍历原链表时按条件尾插到两条链表，最后把小链表尾部接到大链表头部，并断开大链表尾部的旧 next。

详细版

例如：

1 -> 4 -> 3 -> 2 -> 5 -> 2, x=3
结果:
1 -> 2 -> 2 -> 4 -> 3 -> 5

要保持相对顺序，不能简单左右交换。正确做法是维护 smallTail 和 largeTail，扫描到小于 x 的节点接到 small，其他接到 large。最后 smallTail.next = largeDummy.next，largeTail.next = null，防止旧指针形成环。

完整版教学

一、分隔链表的目标不是排序

题目只要求把小于 x 的节点放前面，大于等于 x 的节点放后面，并保持两部分内部的原相对顺序。

input:  1 -> 4 -> 3 -> 2 -> 5 -> 2, x=3
output: 1 -> 2 -> 2 -> 4 -> 3 -> 5

注意 4,3,5 的相对顺序没变，1,2,2 的相对顺序也没变。这不是快排 partition 的不稳定交换版本。

记忆钩子：链表分隔是“两条链表收集”，不是原地乱换。

二、为什么用两个 dummy

我们需要构造两条结果链表：small 和 large。每条链表都要处理“第一次插入”的头节点问题，所以用两个 dummy 最清爽。

smallDummy -> 小于 x 的节点
largeDummy -> 大于等于 x 的节点

同时维护两个尾指针：

ListNode smallTail = smallDummy;
ListNode largeTail = largeDummy;

这样每来一个节点，都能 O(1) 尾插到对应链表。

三、遍历时按条件尾插

核心代码：

while (head != null) {
  if (head.val < x) {
    smallTail.next = head;
    smallTail = smallTail.next;
  } else {
    largeTail.next = head;
    largeTail = largeTail.next;
  }
  head = head.next;
}

这个版本还缺一个关键细节：移动 head 前最好保存 next，或者最后一定要断尾。因为节点原来的 next 仍然保留，可能把两条链串乱。

更稳写法：

ListNode next = head.next;
head.next = null;
// 接到 small 或 large
head = next;

提前断开能减少环和旧连接问题。

四、最后拼接两条链表

遍历完成后：

small: 1 -> 2 -> 2
large: 4 -> 3 -> 5

拼接：

smallTail.next = largeDummy.next;
largeTail.next = null;
return smallDummy.next;

如果所有节点都小于 x，largeDummy.next 是 null，也能自然处理。如果所有节点都大于等于 x，smallDummy.next 为空，直接返回 large 链表需要注意；通常可以先拼接再返回：

smallTail.next = largeDummy.next;
return smallDummy.next;

当 small 为空时，smallTail 仍是 smallDummy，返回 smallDummy.next 正好是 large 头。

五、为什么不能用数组式交换思路

数组 partition 常用左右指针交换，速度快但不稳定。链表题要求保持相对顺序时，交换节点会破坏顺序。

方法	是否保持顺序	适合
两条链表尾插	保持	本题标准做法
左右交换值	不一定	不要求稳定时
收集到数组再重建	保持	但额外空间 O(n)

链表的优势是节点可以 O(1) 接到尾部，只要维护 tail 就能稳定分组。

六、复杂度和断链细节

每个节点访问一次，时间 O(n)。两个 dummy 和几个指针，额外空间 O(1)。

断链是高频易错点。输入链表节点原本连在一起，如果不把 large 的尾部 next 置空，可能出现：

largeTail.next still points to old node
-> result contains extra nodes
-> even forms cycle

所以最后 largeTail.next = null 是安全习惯。

七、常见误区与追问

误区：分隔链表就是排序链表。 只要求按 x 分两区，区内相对顺序保持。
误区：可以直接交换节点值。 交换值可能破坏稳定性，也不符合重连节点的题意。
误区：拼接后不用断尾。 原链表旧 next 可能造成多余连接或环。
追问：为什么用两个 dummy？ 避免分别处理 small 和 large 第一次插入的头节点。
追问：空间复杂度为什么是 O(1)？ 没创建新业务节点，只重用原节点并用常数指针。
追问：如果全部小于 x 或全部大于等于 x 怎么办？ dummy 拼接逻辑能自然覆盖这些边界。

八、加强记忆

分隔链表记成“两桶稳定收集”。一个 dummy 收小节点，一个 dummy 收大节点，遍历原链表时尾插到对应桶，最后 small 接 large。关键是保持相对顺序，不要用数组式不稳定交换；收尾时要断开 largeTail.next，防止旧指针把结果链表污染。

简化版

详细版