LeetCode 面试题 02.04. 分割链表

约 4 分钟
文章信息 8 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 程序员面试金典（第 6 版） 快手 猿辅导
标签
双指针 链表

题目描述

✅ 面试题 02.04. 分割链表

image-20260928224015052

image-20260928224015053

题意分析

重新连接链表，使所有小于 x 的节点都位于大于或等于 x 的节点之前；等于 x 的节点属于后一组。题目不要求保留组内原始顺序，本文采用尾插法，得到的结果会同时保留两组各自的相对顺序。

这里只按阈值分组，不需要把每组内部排序，也不需要为原有数据重新创建节点。

解法：双链表拼接

核心思路

[!blue]

分别用 smallDummy、bigDummy 作为两组的虚拟头，small、big 指向各组已经收集到的最后一个节点。虚拟头不属于结果中的数据，用来统一处理“这一组还没有节点”的情况。

按原链表顺序遍历。当前值小于 x 就令 small.next = head，再将 small 移到当前节点；否则同样追加到 big 尾部。每个节点只进入一组，并且始终追加在该组末尾，因此从虚拟头到尾指针这一段，正好是已经访问过的对应组节点，顺序也与原链表一致。

追加时修改的是该组原尾节点的 next，当前节点自己的 next 尚未改动，所以仍能通过 head = head.next 找到原链表的下一个节点。不过，组尾暂时保留的旧连接可能指向另一组，不能把它当作最终链表的一部分。

遍历结束后，先令 big.next = null，清除后半组尾节点残留的旧连接；再令 small.next = bigDummy.next，用后半组头部替换前半组尾部的旧连接。这样两组之间只有一次从小值组到大值组的连接，最后以空指针结束，所有原节点恰好出现一次。

如果小值组为空，small 仍是虚拟头，连接后直接指向大值组；如果大值组为空，bigDummy.next 为空，连接操作便把小值组正确收尾。空链表也沿用相同逻辑，最终返回 smallDummy.next。

解题步骤

  1. 准备两组虚拟头，两个尾指针分别从各自虚拟头出发。
  2. 遍历原链表，根据 head.val < x 将当前节点追加到对应组，再沿原后继继续。
  3. 将 big.next 置空，清除后半组尾部的旧连接。
  4. 将 small.next 指向 bigDummy.next，返回 smallDummy.next。

代码实现

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)$，每个原节点只遍历、分组一次。
  • 空间复杂度：$O(1)$，复用原节点，只创建两个虚拟头并使用少量指针。

关键点总结

[!green]

  • 等于 x 的节点进入大值组。
  • 某一组为空时，虚拟头仍让连接逻辑一致。

易错点总结

[!yellow]

  • 忽略大值组断尾，旧连接可能形成环。
  • 把等于 x 的节点放入小值组，会破坏“小值组必须严格小于 x”的划分条件。
  • 返回已经遍历到空的当前指针，会丢失结果入口。

相似题目

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