LeetCode 86. 分隔链表

约 4 分钟
文章信息 14 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 需加强 20-50 面试经典 150 题 腾讯 字节 微软 美团 小米 百度 猿辅导
标签
双指针 链表

题目描述

✅ 86. 分隔链表

image-20260928201444775

image-20260928201444777

题意分析

根据给定值 x 把链表分成两组：所有值小于 x 的节点放在前面，所有值大于或等于 x 的节点放在后面，并返回新的头节点。

两组内部都必须保持节点在原链表中的相对顺序，因此这不是对整条链表排序，也不能把每组倒过来。节点值等于 x 时属于后组，所有原节点都要恰好保留一次。

解法：双哑节点稳定分区

核心思路

[!blue]

从头到尾扫描原链表，将每个节点追加到它所属组的末尾。扫描顺序就是原顺序，尾插又不会改变已收集节点的顺序，因此两组各自都能自然保持稳定。

为两组各建一个哨兵和尾指针。哨兵只作为连接起点，不参与结果；即使某一组暂时为空，也能统一执行“尾部接当前节点，再移动尾指针”。

当前节点还带着原来的后继连接，不能直接把它当成独立节点使用。每轮先保存 next，再把当前节点的后继置空，然后按 < x 或 >= x 追加到对应组。这样两条已收集的链始终独立、末尾为空，未处理部分则始终由保存的 next 指向，不会丢节点或保留跨组旧连接。

扫描结束时，两条链已经分别包含全部小值节点和其余节点。将小链尾部接到大链头部，便满足整体分组要求，同时两组内部顺序不变。若小链为空，它的尾指针仍是哨兵，连接操作也能直接把答案指向大链；原链为空或大链为空同样不需要额外分支。

解题步骤

  1. 创建两个哨兵 smallDummy、largeDummy，对应尾指针最初指向各自哨兵。
  2. 对当前节点先保存原后继，再将当前后继置空。
  3. 节点值小于 x 时追加到小链末尾，否则追加到大链末尾，并移动相应尾指针。
  4. 使用保存的原后继继续扫描，直至处理完全部节点。
  5. 把小链尾部接到 largeDummy.next，返回 smallDummy.next。

代码实现

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
}

复杂度分析

设链表长度为 $n$。

  • 时间复杂度：$O(n)$，每个节点只扫描并追加一次。
  • 辅助空间复杂度：$O(1)$，只创建两个哨兵并维护常数个指针，结果复用原链表节点。

关键点总结

[!green]

  • 按原顺序扫描并尾插，才能同时保证两组的相对顺序。
  • 先保存后继再断开旧连接，使已收集部分与未处理部分各自清楚。
  • 两个哨兵统一处理首节点、空链和某一组为空的情况。

易错点总结

[!yellow]

  • 分组条件必须为 < x 和 >= x，不能把等于 x 的节点放入前组。
  • 头插会反转每组的相对顺序，不满足稳定分组要求。
  • 先断链再保存后继，会失去通往原链剩余节点的入口。
  • 复用节点时若不清理原连接，最终拼接可能留下跨组指向甚至形成环。
  • 返回时要跳过哨兵，不能把占位节点当成原链中的真实节点。

相似题目

题目 难度 关联与区别
328. 奇偶链表 中等 同样稳定拆成两条链再连接，本题按值与x比较分组，原题按下标奇偶分组。
21. 合并两个有序链表 简单 同样使用哑节点和尾指针连接节点，本题维护两组各自原顺序而不是按大小归并。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/63245444
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！