LeetCode 面试题 02.04. 分割链表

2025-06-21 HGNULB 约 9 分钟

文章信息 8 个分类 2 个标签

分类

LeetCode CodeTop 中等未解决 2-5 快手猿辅导程序员面试金典（第 6 版）

题目描述

✅ 面试题 02.04. 分割链表

题意分析

给一条单链表和一个基准值 x，要求重排节点，使得所有值小于 x 的节点都排在所有值大于等于 x 的节点之前。返回重排后的头节点。

题目只要求「小的在前、大的在后」这一个划分性质，并没有要求整体有序，也没有要求 x 本身出现在分界点上。这是本题最容易被误读的地方——它不是排序，只是一次分区。

注意这是链表而不是数组。数组做分区可以像快排那样双指针对撞交换元素，但链表拿不到前驱、也没有随机访问，交换节点的代价远高于改指针。链表的天然优势恰恰是摘下来重新接几乎零成本，这个特性直接指向解法。

还要看清返回的是「重排后的链表」而不是新建的链表。虽然新建节点也能通过，但既然原节点可以直接复用，$O(1)$ 额外空间是理所应当的目标。

边界有三种需要单独想清楚：链表为空；所有节点都小于 x（大值那侧一个节点都没有）；所有节点都大于等于 x（小值那侧为空，返回的头节点不再是原 head）。好的实现应该让这三种情况自然落进主逻辑，不需要额外分支。

解法：双链表拼接

核心思路

先想在原链表上就地调整：遍历时遇到大值节点就把它往后挪。这需要频繁地找前驱、断链、再插入到某个位置，每次插入还要维护「已处理部分的边界」，指针操作复杂且容易出错，最坏还会退化成 $O(n^2)$。瓶颈在于试图在一条链上同时维护两类节点的相对位置。

观察到分区的本质是把节点分成两类、类内保持原顺序、最后小类整体接在大类前面。既然如此，为什么不干脆拆成两条独立的链？每条链只收一类节点，各自只需维护一个尾指针，追加是 $O(1)$；两条链都建好后，一次拼接就完成全部工作。

这就是「分桶后拼接」的思路。为了让两条新链的第一次追加不用特判（否则每次都要判断「这是不是这条链的第一个节点」），给每条链各配一个哑节点作为固定的起点，真正的头节点永远是 dummy.next。

循环维持的不变量是：每处理完一个原节点，small 指向小值链的当前尾节点、big 指向大值链的当前尾节点，两条链上的节点合起来恰好是原链表已遍历的前缀，且各自保持了原有的相对顺序。每一轮把当前节点按 val < x 追加到对应链尾并推进该链的尾指针，不变量得以维持。

循环结束后还有一步不能忘：big.next = null。因为大值链的尾节点仍然保留着它在原链表里的 next 指针，那个指针可能指回小值链上的某个节点，直接拼接就会形成环。断尾之后再执行 small.next = bigDummy.next，把小值链的尾接到大值链的头，最后返回 smallDummy.next。

这个写法一趟遍历、只用常数个指针、不新建任何数据节点，是面试官期待的标准答案。

解题步骤

建两个哑节点 smallDummy 与 bigDummy，各配一个尾指针 small、big 初始指向自己：哑节点的作用是让「第一次追加」和「后续追加」写成同一行代码，彻底消除对空链的特判，也让返回值永远能从 dummy.next 取到。

遍历原链表，条件用 head != null：这里直接把 head 当游标复用是安全的，因为每轮修改的是上一个节点的 next（即 small.next 或 big.next），当前节点自身的 next 还没被动过，所以 head = head.next 仍然取得到原来的后继。

按 head.val < x 分流：小于 x 走小链，否则走大链。判断必须是严格小于——等于 x 的节点按题意属于「大于等于」那一侧。

追加两步走：先 small.next = head，再 small = small.next：前一步把节点挂到链尾，后一步让尾指针跟上。顺序不能反，先动尾指针就会挂错位置。

推进 head = head.next：注意此时 head 已经被挂进某条新链，但它的 next 还是原来的值，所以这一行读到的仍是原链表的下一个节点。

循环结束后先执行 big.next = null：这一行是全题的关键。大值链的尾节点还携带着原链表里的 next，不切断就会在拼接后成环。而小值链的尾不需要单独置空，因为下一步马上会给它赋新值。

执行 small.next = bigDummy.next 完成拼接：bigDummy.next 就是大值链的真正头节点；若大值链为空，它是 null，赋值后小值链正确地以 null 收尾，无需特判。

返回 smallDummy.next：不能返回原 head——原头节点如果是个大值，它在结果里会跑到后半段。若小值链为空，smallDummy.next 正好是大值链的头，也是对的。

以 head = 1 → 4 → 3 → 2 → 5 → 2、x = 3 走一遍（S: 表示小值链、B: 表示大值链，均省略哑节点）。

初始：S: 空，B: 空。

节点 1：1 < 3，挂到小链，S: 1。

节点 4：4 >= 3，挂到大链，B: 4。

节点 3：3 >= 3（等于也归大侧），B: 4 → 3。

节点 2：2 < 3，S: 1 → 2。

节点 5：5 >= 3，B: 4 → 3 → 5。

节点 2：2 < 3，S: 1 → 2 → 2。

遍历结束，small 指向最后那个 2，big 指向 5。此时节点 5 的 next 在原链表里正是最后那个 2，如果不断尾直接拼接，就会得到 1 → 2 → 2 → 4 → 3 → 5 → 2 → ... 并从 5 绕回 2 形成环。执行 big.next = null 后，再 small.next = bigDummy.next 得到 1 → 2 → 2 → 4 → 3 → 5 → null，返回 smallDummy.next 即节点 1。

可以看到两侧内部都保持了原有的相对顺序（小侧 1、2、2，大侧 4、3、5），并且分区性质成立。再看极端用例 head = 5 → 6、x = 3：小链始终为空，smallDummy.next 在拼接后等于 bigDummy.next，返回 5 → 6，主逻辑天然覆盖。

代码实现

class Solution {
    // 保持原有相对顺序，最后把两条链表连接起来。
    public ListNode partition(ListNode head, int x) {
        ListNode smallDummy = new ListNode(0);
        ListNode bigDummy = new ListNode(0);
        ListNode small = smallDummy;
        ListNode big = bigDummy;

        while (head != null) {
            if (head.val < x) {
                small.next = head;
                small = small.next;
            } else {
                big.next = head;
                big = big.next;
            }
            head = head.next;
        }
        big.next = null;
        small.next = bigDummy.next;

        return smallDummy.next;
    }
}

func partition(head *ListNode, x int) *ListNode {
    // 保持原有相对顺序，最后把两条链表连接起来。
    smallDummy := &ListNode{}
    bigDummy := &ListNode{}
    small := smallDummy
    big := bigDummy

    for head != nil {
        if head.Val < x {
            small.Next = head
            small = small.Next
        } else {
            big.Next = head
            big = big.Next
        }
        head = head.Next
    }
    big.Next = nil
    small.Next = bigDummy.Next

    return smallDummy.Next
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是链表节点数。只遍历一趟，每个节点做一次比较和两次指针赋值；末尾的断尾与拼接是常数次操作。

空间复杂度：$O(1)$，只额外创建了两个哑节点和 small、big 两个尾指针，与链表长度无关。全程复用原有节点，没有新建任何数据节点。

关键点总结

链表要按某个条件重排时，拆桶再拼接几乎总是优于在原链上就地挪动：追加是 $O(1)$、类内顺序自动保持、指针操作只有两行，这个套路在奇偶链表、按奇偶排序等题里直接复用。

哑节点消除头部特判是链表题的通用技巧。凡是「结果的头节点可能不是原 head」或者「可能要往空链上追加」，先建哑节点几乎不会错。

拼接前必须断开后一段的尾指针，否则残留的旧 next 会把链接回前面形成环——这是分桶类链表题唯一的隐藏陷阱，也是面试官最爱追问的一点。

复用 head 作游标是安全的，前提是每轮修改的都是上一个节点的 next；写链表代码时养成「这一行改的是谁的指针」的自问习惯，就能判断要不要先暂存后继。

本题只要求分区不要求有序，识别出这一点才能把复杂度从排序的 $O(n \log n)$ 降到 $O(n)$；面试时先确认「需不需要整体有序」是很自然的澄清提问。

易错点总结

忘记 big.next = null：1 → 4 → 3 → 2、x = 3 时，大链尾是节点 3，它的旧 next 仍指向节点 2，拼接后 2 → 4 → 3 → 2 成环，遍历结果时直接死循环。

返回 head 而不是 smallDummy.next：4 → 1、x = 3 时原 head 是 4，它在结果里排在第二位，返回它只能得到 4 → null，丢掉了前面的 1。

判断写成 head.val <= x：x = 3 且链表含节点 3 时，3 会被划进小值区，1 → 3 → 2、x = 3 会返回 1 → 3 → 2，而 3 本应排在 2 后面。

追加顺序写反成先 small = small.next 再 small.next = head：small.next 此刻还是旧值甚至是 null，第一轮就会抛空指针。

不用哑节点、直接判断链是否为空来决定头指针：代码里会出现四个分支（小链空/非空 × 大链空/非空），5 → 6、x = 3 这类小链全空的用例极易漏掉头指针的赋值，返回 null。

两条链共用一个哑节点：smallDummy 和 bigDummy 若指向同一个对象，第二次赋值会覆盖第一次，1 → 4 会退化成只剩一个节点。

在循环里就执行拼接 small.next = bigDummy.next：大链还没建完，1 → 4 → 2 会把尚不完整的大链接进去，随后大链继续追加又改动了同一段指针，结果顺序错乱。

误以为要整体排序而调用排序逻辑：3 → 1 → 2、x = 3 的合法答案是 1 → 2 → 3，但 2 → 1 → 3 同样合法；按排序写不仅多花 $O(n \log n)$，还可能在要求「保持类内相对顺序」的变体里给出与预期不符的输出。

新建节点复制值来构造两条链：空间退化为 $O(n)$，而且如果节点上挂着其他字段（面试官常追加这个条件），复制方案直接不成立。

循环里先写 head = head.next 再做追加：当前节点被跳过，1 → 2 会漏掉节点 1，返回 2 → null。

相似题目

题目	难度	考察点
86. 分隔链表	中等	与本题同题，但明确要求保留两个分区内节点的原始相对顺序
328. 奇偶链表	中等	按下标奇偶而非节点值分桶，可省掉一个哑节点直接用原头节点当锚点
21. 合并两个有序链表	简单	拼接的逆操作：两条链合成一条，同样靠哑节点消除头部特判
148. 排序链表	中等	真正要求整体有序，需归并分治，本题的分桶只是其中一步
61. 旋转链表	中等	同样是断开再重接，难点在于先成环再按位置断开
143. 重排链表	中等	拆成两段后交替合并而非顺序拼接，还需先反转后半段
75. 颜色分类	中等	数组上的三路分区，用对撞指针原地交换，与链表改指针的手法完全不同
905. 按奇偶排序数组	简单	数组版二分区，不要求类内顺序时可用双指针一趟交换
922. 按奇偶排序数组 II	简单	要求奇偶交替落位，分桶后还需按下标奇偶回填