力扣解题-86. 分隔链表

力扣解题-86. 分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：
输入：head = [2,1], x = 2
输出：[1,2]

提示：
链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200

Related Topics
链表、双指针

第一次解答

解题思路

核心方法：双哑节点分治（新建节点版），通过两个哑节点分别构建“小于x的链表”和“大于等于x的链表”，遍历原链表后将两个链表拼接，逻辑直观且能保证节点相对顺序，但会创建新节点（额外空间开销）。

核心逻辑拆解

分隔链表的核心是“分类收集+顺序拼接”，且需保留原节点的相对位置：

具体步骤（以示例1 head=[1,4,3,2,5,2]、x=3为例）

性能说明

• 时间复杂度：O(n)（仅一次线性遍历原链表，n为节点数）；
• 空间复杂度：O(n)（创建了n个新节点存储结果，额外空间开销）；
• 优势：
• 逻辑简单易懂，分类收集的思路符合直觉；
• 完美保留两个分区的节点初始相对位置；
• 双哑节点避免了头节点为空的边界问题；
• 可优化点：无需创建新节点，直接复用原链表节点可将空间复杂度降至O(1)。

public ListNode partition(ListNode head, int x) {
ListNode smallDummy=new ListNode(0);
ListNode small=smallDummy;
ListNode bigDummy=new ListNode(0);
ListNode big=bigDummy;

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

示例解答

解题思路

解法1：双哑节点优化版（复用原节点，O(1)额外空间）

核心方法：双哑节点+复用原节点，在第一次解答的分治思路基础上，直接复用原链表节点（不创建新节点），仅调整节点的next指针，额外空间复杂度优化为O(1)，是工程中更优的实现方式。

代码实现

public ListNode partition(ListNode head, int x) {
// 小值链表哑节点
ListNode smallDummy = new ListNode(0);
ListNode small = smallDummy;
// 大值链表哑节点
ListNode bigDummy = new ListNode(0);
ListNode big = bigDummy;

ListNode curr = head;
while (curr != null) {
// 保存下一个节点，避免断链
ListNode next = curr.next;
// 断开当前节点与原链表的连接
curr.next = null;

if (curr.val < x) {
small.next = curr; // 直接复用原节点
small = small.next;
} else {
big.next = curr; // 直接复用原节点
big = big.next;
}
curr = next;
}

// 拼接两个链表
small.next = bigDummy.next;
return smallDummy.next;
}

优势说明

• 时间复杂度：O(n)，与原解法一致；
• 额外空间复杂度：O(1)（仅使用两个哑节点和指针，无新节点创建）；
• 核心优化点：
• 复用原链表节点，避免新节点创建的内存开销；
• 遍历过程中保存curr.next并断开当前节点，防止原链表的指针干扰新链表；
• 逻辑与原解法一致，仅节点处理方式优化，易理解易迁移。

解法2：单指针遍历拼接法（思路拓展）

核心方法：先找分界点再拼接，通过一次遍历找到第一个≥x的节点的前驱，将后续所有小于x的节点移动到分界点前，无需额外哑节点（仅需O(1)空间），但逻辑稍复杂。

代码实现

public ListNode partition(ListNode head, int x) {
if (head == null) {
return null;
}
// 哑节点处理头节点小于x的情况
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;

// 第一步：找到第一个≥x的节点的前驱
while (pre.next != null && pre.next.val < x) {
pre = pre.next;
}
// 此时pre是最后一个小于x的节点，pre.next是第一个≥x的节点
ListNode curr = pre;

// 第二步：遍历后续节点，将小于x的节点移动到pre后
while (curr.next != null) {
if (curr.next.val < x) {
// 取出小于x的节点
ListNode moveNode = curr.next;
curr.next = moveNode.next;
// 插入到pre后
moveNode.next = pre.next;
pre.next = moveNode;
// pre后移
pre = pre.next;
} else {
curr = curr.next;
}
}

return dummy.next;
}

适用场景说明

• 时间复杂度：O(n)（一次遍历完成所有操作）；
• 空间复杂度：O(1)（仅使用指针变量）；
• 优势：无需创建新链表，仅通过指针调整完成分隔，空间效率最优；
• 局限性：逻辑稍复杂，需要精准处理节点的插入/移动，新手易出错。

总结