链表中等1 种解法

#86分隔链表

稳定地把小于 x 的节点放到其余节点之前，同时保持两组内部的原相对顺序。

#链表#双指针

解题主线

用两条临时链表分别收集小于 x 和大于等于 x 的节点，最后拼接。

逐个摘取原节点可以保持稳定顺序，无需创建值节点。

解法 1：双链表稳定分区

扫描原链表，将节点追加到 before 或 after 尾部，断开 after 尾部后连接两条链表。

时间复杂度

O(n)

空间复杂度

O(1)

86. 分隔链表 · 双链表稳定分区

java

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;
            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;
    }
}

扫描原链表，将节点追加到 before 或 after 尾部，断开 after 尾部后连接两条链表。

边界与易错点

必须把大于等于 x 的链表尾部置 null，否则旧 next 可能形成环。
先保存 next 再断开当前节点，不能在断链后读取 current.next。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

Q086_partition.java