链表中等1 种解法
#86分隔链表
稳定地把小于 x 的节点放到其余节点之前，同时保持两组内部的原相对顺序。
#链表#双指针
原题
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
输入：head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2 输出：[1,2]
提示：
- 链表中节点的数目在范围
[0, 200]内 -100 <= Node.val <= 100-200 <= x <= 200
解题主线
- 用两条临时链表分别收集小于 x 和大于等于 x 的节点，最后拼接。
- 逐个摘取原节点可以保持稳定顺序，无需创建值节点。
解法 1：双链表稳定分区
扫描原链表，将节点追加到 before 或 after 尾部，断开 after 尾部后连接两条链表。
-
时间复杂度： O(n)
-
空间复杂度： O(1)
public class Solution {
static final class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public ListNode partition(ListNode head, int x) {
ListNode beforeDummy = new ListNode(0);
ListNode afterDummy = new ListNode(0);
ListNode before = beforeDummy;
ListNode after = afterDummy;
for (ListNode current = head; current != null; ) {
// 断链前保存后继，确保扫描指针不会丢失。
ListNode next = current.next;
// 摘下当前节点，避免旧 next 把两个分区意外串联成环。
current.next = null;
// 两条尾插链分别保持各自节点的原相对顺序。
if (current.val < x) {
before.next = current;
before = current;
} else {
after.next = current;
after = current;
}
current = next;
}
// 小值链尾连接大值链头，虚拟头统一处理任一分区为空的边界。
before.next = afterDummy.next;
return beforeDummy.next;
}
}边界与易错点
- 必须把大于等于 x 的链表尾部置 null，否则旧 next 可能形成环。
- 先保存 next 再断开当前节点，不能在断链后读取 current.next。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
Q086_partition.java