分隔链表

看到 1→2→2→4→3→5 很多人以为要排序——其实 4 还在 3 前面、根本没排好。规则只有一条:小的整体在前、大的整体在后,每堆内部保持原来的先后。

准备两条空链表,各自焊一个哑节点:small 专收小于 x 的,large 专收大于等于 x 的。原链表从头扫一遍,每个节点按值丢进对应的链;扫完把 small 的尾巴接到 large 的头,大功告成。

起手 · 三条链就位：上面是原链表,cur 站在头节点 1。下面两条是空链:small(Sd 哑头)、large(Ld 哑头),各有一个尾指针 sp / lp 守在自己哑头上,等着往后挂节点。

判定规则 · 拿每个值和 x=3 比：判据只有一条:看 cur 当前节点的值。小于 3 就挂到 small 尾,大于等于 3 就挂到 large 尾。下面一格一格走给你看。

看 cur = 1 · 1 < 3 ?：cur 的值是 1,1 &lt; 3 成立 → 归 small。把节点 1 挂到 small 链的尾巴上(标绿),原链里它也标绿表示「已分流」。

sp 跟到新尾 · cur 前移：尾指针 sp 跟着前移到刚挂上的 1(成为新的尾)。原链 cur 往后走一格,来到 4,继续判断。

看 cur = 4 · 4 < 3 ?：cur 的值是 4,4 ≥ 3 → 归 large。把节点 4 挂到 large 链尾(标红),原链里 4 也标红表示进了大堆。

lp 跟到新尾 · cur 前移：尾指针 lp 跟到 large 新尾 4。原链 cur 前移到 3。

看 cur = 3 · 3 < 3 ?：cur 是 3。判定条件是 小于 x,3 不小于 3(等于也算大堆) → 归 large。把 3 挂到 large 尾(标红)。这一格就是雷区:用的是 < 不是 ≤。

lp 跟到新尾 · cur 前移：lp 跟到 large 新尾 3。原链 cur 前移到第一个 2。

看 cur = 2 · 2 < 3 ?：cur 是第一个 2,2 &lt; 3 → 归 small。挂到 small 尾(标绿),它接在 1 后面,顺序自然保住。

sp 跟到新尾 · cur 前移：sp 跟到 small 新尾(第一个 2)。原链 cur 前移到 5。

看 cur = 5 · 5 < 3 ?：cur 是 5,5 ≥ 3 → 归 large。挂到 large 尾(标红),接在 3 后面。

lp 跟到新尾 · cur 前移：lp 跟到 large 新尾 5。原链 cur 前移到最后一个 2。

看 cur = 2 · 2 < 3 ?：最后一个 2,2 &lt; 3 → 归 small,挂到 small 尾(标绿)。它排在前一个 2 后面——两个 2 的先后被完整保留。

sp 跟到新尾 · cur 到尾：sp 跟到 small 最后的 2。原链 cur 已走到 null,整条扫完。绿格全归 small、红格全归 large——分流完毕,只差拼接。

对照 · 两堆都保住了原序：停下来看一眼:small 里 1→2→2、large 里 4→3→5,两堆内部都严格保持原链顺序(尾插的天然结果)。注意 large 是 4→3→5,根本没排序——这正符合题意。

收尾 1 · large 尾必须断开：拼接前先把 large 的尾巴 lp.next 置为 null。为什么?最后那个 5 在原链里本来还连着别的指针残留,不断开会成环或拖出多余节点。这一步是最容易漏的雷。

收尾 2 · small 尾接 large 头：关键一接:让 small 的尾 sp.next 指向 large.next(也就是 large 的第一个真节点 4)。small 的 1→2→2 后面直接续上 large 的 4→3→5。

拼好的整条链 · 哑头还在最前：现在整条链是 Sd→1→2→2→4→3→5,绿色是原来 small 的 3 个,后半段刚接上的 4→3→5 是 large 段。哑头 Sd 还杵在最前面,得跳过它。

完成 · 返回 small.next：返回 small.next(跳过哑头 Sd),就是最终链 1→2→2→4→3→5。小的整体在前、大的整体在后,且各堆内部原序未变——完美符合题意。

一句话记牢:small 收小、large 收大,扫完 large 尾置 null 再把 small 尾接 large 头,返回 small.next。

雷区实演 · 漏断 large 尾 = 成环：如果忘了 lp.next = null:原链里 5 后面那个 2 早被搬进 small 了,5 的 next 还指着它,于是链尾 5 回头指向 2 形成环(尾部 ↺)。遍历这条链会死循环。这就是必须收口的原因。

边界三连：空链、全进小堆、全进大堆——三种极端下,双哑头写法都不用特判:空堆自然就是「哑头.next = null」,拼接照常成立。

面试追问 1：稳定性来自「顺序扫描 + 尾插」,这是分区类链表题的通用保证。

面试追问 2：哑节点把所有特殊情况抹平成一种通用写法,是链表题的万金油。

面试追问 3：能想到原地法是加分项,但工程上双哑头更稳,讲清取舍即可。

这题学完别乱跳,去 链表专题 连刷同类「双指针 + 哑头」题;卡住了可以随时在页面里提问「为什么这一步成立」。