Leetcode: 86 Partition List

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

Example:

Input: head = [2,1], x = 2
Output: [1,2]

问题

给定链表的 head 和一个值 x，将链表重新排列，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应该保留两个分区中每个节点的原始相对顺序。

解决方案

双指针法

Approach / 方法

This solution uses two pointers to create two separate lists: one for nodes less than x and another for nodes greater than or equal to x. After traversing the entire list, we connect the two lists to form the final partitioned list.

该解决方案使用两个指针创建两个单独的链表：一个用于存储小于 x 的节点，另一个用于存储大于或等于 x 的节点。在遍历完整个链表后，我们将这两个链表连接起来，形成最终的分区链表。

Implementation / 实现

python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        # Create two dummy nodes
        less_head = ListNode(0)
        greater_head = ListNode(0)

        # Pointers for the two lists
        less = less_head
        greater = greater_head

        # Traverse the original list
        while head:
            if head.val < x:
                less.next = head
                less = less.next
            else:
                greater.next = head
                greater = greater.next
            head = head.next

        # Connect the two lists
        greater.next = None  # To prevent a cycle in the list
        less.next = greater_head.next

        return less_head.next

Explanation / 解释

Create Dummy Nodes / 创建虚拟节点
```
less_head = ListNode(0)
greater_head = ListNode(0)
```
- English: We create two dummy nodes less_head and greater_head to act as the starting points for the two lists that will store nodes less than x and nodes greater than or equal to x, respectively.
- Chinese: 我们创建两个虚拟节点 less_head 和 greater_head，分别作为存储小于 x 的节点和存储大于或等于 x 的节点的两个链表的起始点。
Initialize Pointers for the Two Lists / 初始化两个链表的指针
```
less = less_head
greater = greater_head
```
- English: We initialize pointers less and greater to traverse and build the two separate lists.
- Chinese: 我们初始化指针 less 和 greater 来遍历和构建两个单独的链表。
Traverse the Original List / 遍历原始链表
```
while head:
```
- English: We traverse the original linked list using the head pointer.
- Chinese: 我们使用 head 指针遍历原始链表。
Partition the Nodes / 分区节点
```
if head.val < x:
   less.next = head
   less = less.next
else:
   greater.next = head
   greater = greater.next
```
- English: If the current node’s value is less than x, we add it to the less list. Otherwise, we add it to the greater list.
- Chinese: 如果当前节点的值小于 x，我们将其添加到 less 链表中。否则，我们将其添加到 greater 链表中。
Move to the Next Node / 移动到下一个节点
```
head = head.next
```
- English: We move the head pointer to the next node in the original list.
- Chinese: 我们将 head 指针移动到原始链表中的下一个节点。
Connect the Two Lists / 连接两个链表
```
greater.next = None
less.next = greater_head.next
```
- English: After traversing the original list, we connect the less list to the greater list and set the greater list’s next pointer to None to avoid cycles.
- Chinese: 在遍历完原始链表后，我们将 less 链表连接到 greater 链表，并将 greater 链表的 next 指针设置为 None 以避免形成环。
Return the Partitioned List / 返回分区后的链表
```
return less_head.next
```
- English: We return the partitioned list starting from the first node in the less list.
- Chinese: 我们返回从 less 链表的第一个节点开始的分区后的链表。

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度: O(n), where n is the number of nodes in the linked list. We traverse the entire list once.
Space Complexity / 空间复杂度: O(1), as we only use a constant amount of extra space for pointers.

Key Concept / 关键概念

Two Pointers / 双指针: This approach efficiently partitions the linked list using two pointers to create two separate lists, which are then combined to form the final result.
双指针: 这种方法通过使用两个指针来创建两个单独的链表，从而高效地分区链表，最后将它们组合形成最终结果。

Summary / 总结

English: The two-pointer approach provides an efficient and clear way to partition a linked list while maintaining the relative order of nodes. It is a practical technique for problems involving reordering or partitioning linked lists.
Chinese: 双指针方法提供了一种高效且清晰的方法来分区链表，同时保持节点的相对顺序。它是处理涉及重新排序或分区链表问题的实用技术。

Tips / 提示

English: Practice using the two-pointer technique on various linked list problems to become familiar with its application and nuances.
Chinese: 在各种链表问题中练习使用双指针技术，以熟悉其应用和细微差别。

Solution Template for Similar Questions / 提示

English: Consider using the two-pointer approach for problems involving partitioning, reordering, or separating linked lists.
Chinese: 对于涉及分区、重新排序或分离链表的问题，考虑使用双指针方法。

5 More Similar Questions / 推荐5问题

Recommended Resources / 推荐资源

English: Practice problems involving linked lists to strengthen your understanding of two-pointer techniques and other linked list operations.
Chinese: 练习涉及链表的问题，以加强对双指针技术和其他链表操作的理解。

Partition List - Linked List - Leetcode 86 by NeetCode

Post Views: 12

CODEBITWAVE