LeetCode 86. 分隔链表

2026-03-23 HGNULB 约 5 分钟

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

分类

LeetCode CodeTop 中等未解决需加强 20-50 字节跳动微软美团腾讯猿辅导百度面试经典 150 题

题目描述

✅ 86. 分隔链表

题意分析

给定一个单链表的头节点和一个整数 $x$，要求重排链表，使得所有值小于 $x$ 的节点都排在所有值大于或等于 $x$ 的节点之前。

分界线是「小于 $x$」与「大于等于 $x$」，等于 $x$ 的节点归入后半部分，这个归属必须在写第一行判断之前就确认清楚。

最关键的约束是：两个部分各自内部的节点必须保持它们在原链表中的相对顺序。这条要求排除了一切会打乱次序的做法，也意味着题目要的不是「把链表按 $x$ 排序」—— 后半部分内部完全可以是乱序的，只要与原顺序一致即可。

边界方面，链表可能为空，也可能所有节点都落在同一侧（全部小于 $x$，或全部大于等于 $x$），这两种极端情况下答案就是原链表本身，但代码路径仍然要能正确走通。节点值允许为负，$x$ 也允许为负，判断只依赖大小比较，不涉及正负号。

解法：双哑节点稳定分区

核心思路

难点不是把节点分成两类，而是分组后仍要保持各自的相对顺序。若在原链表中反复摘除、前插，需要同时维护多个前驱，容易断链；更直接的做法是准备两条临时链：一条收集 val < x 的节点，另一条收集 val >= x 的节点，最后拼接。

两条链都使用哑节点和尾指针。顺序扫描原链表时只做尾插，因此节点进入每条链的顺序就是它在原链表中的顺序。处理节点前先保存 next，再断开旧 next，可以保证临时链始终有明确的尾部，也避免旧指针在拼接后形成环。

不变量是：处理完前 i 个节点后，smallDummy.next 与 largeDummy.next 分别包含其中两类节点，且各自保序，两个尾指针都指向本链最后一个节点。第 i+1 个节点只会被尾插到唯一一条链，不变量保持；扫描结束后把小链尾部接到大链头部，便得到稳定分区结果。

解题步骤

创建 smallDummy、largeDummy 及各自的尾指针。

遍历原链表：先保存当前节点的后继，再把当前节点的 next 置空。

当前值小于 x 时尾插到小链，否则尾插到大链；等于 x 必须进入大链。

用之前保存的后继继续遍历，直到所有节点都恰好处理一次。

令小链尾部指向大链头部，返回 smallDummy.next。

例如 [1,4,3,2,5,2]、x = 3，扫描后两条链分别是 1 -> 2 -> 2 和 4 -> 3 -> 5，拼接得到 1 -> 2 -> 2 -> 4 -> 3 -> 5；两段内部顺序均未改变。

代码实现

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode smallDummy = new ListNode(0);
        ListNode largeDummy = new ListNode(0);
        ListNode smallTail = smallDummy;
        ListNode largeTail = largeDummy;

        while (head != null) {
            ListNode next = head.next;
            head.next = null;
            if (head.val < x) {
                smallTail.next = head;
                smallTail = head;
            } else {
                largeTail.next = head;
                largeTail = head;
            }
            head = next;
        }

        smallTail.next = largeDummy.next;
        return smallDummy.next;
    }
}

func partition(head *ListNode, x int) *ListNode {
    smallDummy := &ListNode{}
    largeDummy := &ListNode{}
    smallTail := smallDummy
    largeTail := largeDummy

    for head != nil {
        next := head.Next
        head.Next = nil
        if head.Val < x {
            smallTail.Next = head
            smallTail = head
        } else {
            largeTail.Next = head
            largeTail = head
        }
        head = next
    }

    smallTail.Next = largeDummy.Next
    return smallDummy.Next
}

复杂度分析

时间复杂度：O(n)。每个节点只访问、比较和连接一次。

空间复杂度：O(1)。只使用两个哑节点和常数个指针，没有复制链表节点。

关键点总结

题目要求的是稳定分区，所以两类节点都必须尾插；头插会反转相对顺序。

哑节点统一处理空链和首节点，最终头节点始终从 dummy.next 取得。

保存后继后再断开当前节点，既不会丢失未处理部分，也能彻底消除旧链关系。

正确的边界是 < x 与 >= x，不是 <= x 与 > x。

易错点总结

把 val == x 放入小链：[1,3,2]、x=3 会错误地把 3 放在分界线前。

使用头插法：[1,2,4,3] 会变成小链 2 -> 1、大链 3 -> 4，破坏稳定性。

先断链再保存后继：执行 head.next = null 后才取下一节点，会在第一个节点处丢失剩余链表。

不处理旧尾指针：若直接复用节点却既不断开当前节点、也不把大链尾部置空，拼接后可能形成环。

返回哑节点本身：结果会多出一个并不存在的值为 0 的节点，应返回 smallDummy.next。

相似题目

题目	难度	考察点
21. 合并两个有序链表	简单	反向操作：把两条链归并成一条，同样靠哑节点尾插
24. 两两交换链表中的节点	中等	局部成对翻转，考的是三指针的顺序而非分段
61. 旋转链表	中等	先成环再定点断开，与本题的「必须断尾」互为镜像
143. 重排链表	中等	拆成两半后需反转后半段再交替拼接，拆分粒度更细
328. 奇偶链表	中等	分组依据是节点位置奇偶而不是节点值大小
725. 分隔链表	中等	按长度均分成 k 段并返回数组，重点在长度分配
面试题 02.04. 分割链表	中等	同构题但不要求保序，可对比尾插与头插的取舍