What is the most efficient way to partition a linked list?

The most efficient way is to use a two-pointer technique, which ensures the solution runs in O(n) time with constant space.

How can I handle edge cases like an empty list?

Edge cases like an empty list are naturally handled by the two-pointer approach, as no nodes will be processed.

What pattern is this problem based on?

This problem is based on linked-list pointer manipulation, where you manage pointers to reorder nodes into partitions.

How can I ensure the relative order is preserved?

You can ensure this by carefully separating nodes into two partitions and linking them while maintaining the original order in each partition.

Can I solve this problem without using extra space?

Yes, the problem can be solved in-place with O(1) space by manipulating the pointers of the existing nodes.

#86

Medium

auto_awesome链表指针操作

LeetCode 题解工作台

分隔链表

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。示例 1：输入： head = [1,4,3,2,5,2], x = 3 输出：[1,2,2,4,3,5] …

链表双指针

题目描述

给你一个链表的头节点 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

lightbulb

解题思路

方法一：模拟

我们创建两个链表 $l$ 和 $r$ ，一个用来存储小于 $x$ 的节点，另一个用来存储大于等于 $x$ 的节点。然后我们将它们拼接起来。

时间复杂度 $O(n)$ ，其中 $n$ 是原链表的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        l = ListNode()
        r = ListNode()
        tl, tr = l, r
        while head:
            if head.val < x:
                tl.next = head
                tl = tl.next
            else:
                tr.next = head
                tr = tr.next
            head = head.next
        tr.next = None
        tl.next = r.next
        return l.next

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate effectively uses pointer manipulation to solve the problem.
question_mark
Candidate correctly handles edge cases like empty lists or all nodes falling in one partition.
question_mark
Solution demonstrates knowledge of linked-list traversal and node manipulation.

warning

常见陷阱

外企场景

error
Failing to preserve the relative order of nodes within each partition.
error
Incorrectly linking the 'less than x' partition to the 'greater than or equal to x' partition.
error
Not considering edge cases like empty lists or lists where all nodes fall into one partition.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to handle circular linked lists.
arrow_right_alt
Partition the list in place using constant space.
arrow_right_alt
Extend the problem by adding multiple partitions around different values.

help

常见问题

外企场景

继续练习

#82 删除排序链表中的重复元素 II #61 旋转链表 #141 环形链表