LeetCode 面试题 02.04. 分割链表

Categories:

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

题目描述

✅ 面试题 02.04. 分割链表

思路分析

解法一：双链表拼接（推荐）

核心思路：

用两个哑节点分别收集小于 x 与大于等于 x 的节点。

保持原有相对顺序，最后把两条链表连接起来。

注意断开大链表尾部，避免形成环。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表长度。

空间复杂度：O(1)，仅使用常数额外空间。

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
}

相似题目

题目	难度	考察点
86. 分隔链表	中等	链表、双指针
328. 奇偶链表	中等	链表重排
143. 重排链表	中等	链表操作
21. 合并两个有序链表	简单	链表
445. 两数相加 II	中等	链表、栈

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/89866580