LeetCode 86. 分隔链表

Categories:

题目描述
思路分析
1. 解法一：双链表模拟（推荐）
相似题目

题目描述

✅ 86. 分隔链表

思路分析

解法一：双链表模拟（推荐）

核心思路：

维护两个虚拟头节点：lessHead 收集所有值 < x 的节点，greaterHead 收集所有值 >= x 的节点。

遍历原链表，按节点值大小分别追加到对应链表尾部，保持原有相对顺序不变。

遍历结束后，将 less 链表的尾部连接到 greater 链表的头部，同时将 greater 链表尾部置为 null，防止形成环。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表节点总数，只需遍历一次。

空间复杂度：O(1)，只使用了常数个额外指针，原地重组节点引用。

class Solution {
    public ListNode partition(ListNode head, int x) {
        // 两个虚拟头节点，分别对应 less 链和 greater 链
        ListNode lessHead = new ListNode(0);
        ListNode greaterHead = new ListNode(0);
        ListNode less = lessHead;
        ListNode greater = greaterHead;

        ListNode cur = head;
        // 遍历原链表，按值大小分配到对应链表
        while (cur != null) {
            if (cur.val < x) {
                less.next = cur;
                less = less.next;
            } else {
                greater.next = cur;
                greater = greater.next;
            }
            cur = cur.next;
        }

        // 断开 greater 链尾部，防止循环引用
        greater.next = null;
        // 将 less 链尾部连接到 greater 链头部
        less.next = greaterHead.next;

        return lessHead.next;
    }
}

func partition(head *ListNode, x int) *ListNode {
    // 两个虚拟头节点，分别对应 less 链和 greater 链
    lessHead := &ListNode{}
    greaterHead := &ListNode{}
    less := lessHead
    greater := greaterHead

    cur := head
    // 遍历原链表，按值大小分配到对应链表
    for cur != nil {
        if cur.Val < x {
            less.Next = cur
            less = less.Next
        } else {
            greater.Next = cur
            greater = greater.Next
        }
        cur = cur.Next
    }

    // 断开 greater 链尾部，防止循环引用
    greater.Next = nil
    // 将 less 链尾部连接到 greater 链头部
    less.Next = greaterHead.Next

    return lessHead.Next
}

相似题目

题目	难度	考察点
21. 合并两个有序链表	简单	链表 / 双指针合并
206. 反转链表	简单	链表 / 迭代与递归
328. 奇偶链表	中等	链表 / 按位置分割重组
148. 排序链表	中等	链表 / 归并排序
143. 重排链表	中等	链表 / 找中点 + 反转 + 合并
876. 链表的中间结点	简单	快慢指针
2. 两数相加	中等	链表 / 虚拟头节点技巧

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/63245444