分隔链表 图解题解

这道题到底在问什么

输入

head = 1→4→3→2→5→2, x = 3

输出

1→2→2→4→3→5

最优解：一步一步想明白

1. 3看到 1→2→2→4→3→5 很多人以为要排序——其实 4 还在 3 前面、根本没排好。规则只有一条:小的整体在前、大的整体在后,每堆内部保持原来的先后。
2. 4准备两条空链表,各自焊一个哑节点:small 专收小于 x 的,large 专收大于等于 x 的。原链表从头扫一遍,每个节点按值丢进对应的链;扫完把 small 的尾巴接到 large 的头,大功告成。
3. 5small / large 都是空哑头上面是原链表,cur 站在头节点 1。下面两条是空链:small(Sd 哑头)、large(Ld 哑头),各有一个尾指针 sp / lp 守在自己哑头上,等着往后挂节点。
4. 6cur 值 < 3 → 小堆;否则大堆判据只有一条:看 cur 当前节点的值。小于 3 就挂到 small 尾,大于等于 3 就挂到 large 尾。下面一格一格走给你看。
5. 71 < 3,归小堆cur 的值是 1,1 < 3 成立 → 归 small。把节点 1 挂到 small 链的尾巴上(标绿),原链里它也标绿表示「已分流」。
6. 8sp=1, cur 移到 4尾指针 sp 跟着前移到刚挂上的 1(成为新的尾)。原链 cur 往后走一格,来到 4,继续判断。
7. 94 ≥ 3,归大堆cur 的值是 4,4 ≥ 3 → 归 large。把节点 4 挂到 large 链尾(标红),原链里 4 也标红表示进了大堆。
8. 10lp=4, cur 移到 3尾指针 lp 跟到 large 新尾 4。原链 cur 前移到 3。
9. 113 ≥ 3,归大堆cur 是 3。判定条件是 小于 x,3 不小于 3(等于也算大堆) → 归 large。把 3 挂到 large 尾(标红)。这一格就是雷区:用的是 < 不是 ≤。
10. 12lp=3, cur 移到 2lp 跟到 large 新尾 3。原链 cur 前移到第一个 2。
11. 132 < 3,归小堆cur 是第一个 2,2 < 3 → 归 small。挂到 small 尾(标绿),它接在 1 后面,顺序自然保住。
12. 14sp=2, cur 移到 5sp 跟到 small 新尾(第一个 2)。原链 cur 前移到 5。
13. 155 ≥ 3,归大堆cur 是 5,5 ≥ 3 → 归 large。挂到 large 尾(标红),接在 3 后面。
14. 16lp=5, cur 移到第二个 2lp 跟到 large 新尾 5。原链 cur 前移到最后一个 2。
15. 172 < 3,归小堆最后一个 2,2 < 3 → 归 small,挂到 small 尾(标绿)。它排在前一个 2 后面——两个 2 的先后被完整保留。
16. 18扫描完成,cur = nullsp 跟到 small 最后的 2。原链 cur 已走到 null,整条扫完。绿格全归 small、红格全归 large——分流完毕,只差拼接。
17. 19small=1,2,2 · large=4,3,5停下来看一眼:small 里 1→2→2、large 里 4→3→5,两堆内部都严格保持原链顺序(尾插的天然结果)。注意 large 是 4→3→5,根本没排序——这正符合题意。
18. 20lp.next = null拼接前先把 large 的尾巴 lp.next 置为 null。为什么?最后那个 5 在原链里本来还连着别的指针残留,不断开会成环或拖出多余节点。这一步是最容易漏的雷。
19. 21sp.next = large.next关键一接:让 small 的尾 sp.next 指向 large.next(也就是 large 的第一个真节点 4)。small 的 1→2→2 后面直接续上 large 的 4→3→5。
20. 22Sd → 1→2→2→4→3→5现在整条链是 Sd→1→2→2→4→3→5,绿色是原来 small 的 3 个,后半段刚接上的 4→3→5 是 large 段。哑头 Sd 还杵在最前面,得跳过它。
21. 23answer = 1→2→2→4→3→5返回 small.next(跳过哑头 Sd),就是最终链 1→2→2→4→3→5。小的整体在前、大的整体在后,且各堆内部原序未变——完美符合题意。
22. 26一句话记牢:small 收小、large 收大,扫完 large 尾置 null 再把 small 尾接 large 头,返回 small.next。
23. 28lp.next 没断 → 5 还指回 2如果忘了 lp.next = null:原链里 5 后面那个 2 早被搬进 small 了,5 的 next 还指着它,于是链尾 5 回头指向 2 形成环(尾部 ↺)。遍历这条链会死循环。这就是必须收口的原因。
24. 35这题学完别乱跳,去 链表专题 连刷同类「双指针 + 哑头」题;卡住了可以随时在页面里提问「为什么这一步成立」。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def partition(self, head, x):
        small = ListNode(0)        # 小堆哑头
        large = ListNode(0)        # 大堆哑头
        sp, lp = small, large      # 两个尾指针
        while head:
            if head.val < x:       # 严格小于才进小堆
                sp.next = head; sp = sp.next
            else:
                lp.next = head; lp = lp.next
            head = head.next
        lp.next = None             # 大堆尾收口,防成环
        sp.next = large.next       # 小堆尾接大堆头
        return small.next

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode small(0), large(0);
        ListNode* sp = &small; ListNode* lp = &large;
        while (head) {
            if (head->val < x) { sp->next = head; sp = sp->next; }
            else { lp->next = head; lp = lp->next; }
            head = head->next;
        }
        lp->next = nullptr;          // 大堆尾收口
        sp->next = large.next;       // 小尾接大头
        return small.next;
    }
};

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode small = new ListNode(0);
        ListNode large = new ListNode(0);
        ListNode sp = small, lp = large;
        while (head != null) {
            if (head.val < x) { sp.next = head; sp = sp.next; }
            else { lp.next = head; lp = lp.next; }
            head = head.next;
        }
        lp.next = null;              // 大堆尾收口
        sp.next = large.next;        // 小尾接大头
        return small.next;
    }
}

复杂度

面试官可能追问