链表分隔问题：保留相对位置

Linked List Partitioning Problem: Preserving Relative Position

Given the head of a linked list and a specific value x, the task is to partition the linked list so that all nodes with values less than x appear before nodes with values greater than or equal to x. Additionally, the relative positions of nodes within each partition must be preserved.

给你一个链表的头节点 head 和一个特定值 x，任务是对链表进行分隔，使得所有值小于 x 的节点都出现在值大于或等于 x 的节点之前。此外，必须保留每个分区中节点的相对位置。

示例

Example

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

解释：在这个示例中，链表被分为两部分：所有值小于 3 的节点 [1, 2, 2] 被放在链表的前半部分，而值大于或等于 3 的节点 [4, 3, 5] 被放在后半部分。所有节点的相对位置得以保留。

Explanation: In this example, the linked list is partitioned into two parts: all nodes with values less than 3 ([1, 2, 2]) are placed in the first part of the list, and nodes with values greater than or equal to 3 ([4, 3, 5]) are placed in the second part. The relative positions of all nodes are preserved.

解题思路

Approach

To solve this problem, we can create two new linked lists:

One list will contain all nodes with values less than x.
The other list will contain all nodes with values greater than or equal to x.

We then combine these two lists to form the final partitioned list while maintaining the relative order of nodes in each partition.

为了解决这个问题，我们可以创建两个新的链表：

一个链表包含所有值小于 x 的节点。
另一个链表包含所有值大于或等于 x 的节点。

然后，我们将这两个链表结合起来，形成最终的分隔链表，同时保持每个分区中节点的相对顺序。

实现步骤

Implementation Steps

Initialize Two Pointers:
- before_head and before to track the start and end of the list of nodes less than x.
- after_head and after to track the start and end of the list of nodes greater than or equal to x.
Traverse the Original List:
- For each node, if its value is less than x, add it to the before list. Otherwise, add it to the after list.
Combine the Two Lists:
- Link the before list to the after_head to combine the two partitions.
- Return before_head.next as the head of the modified list.
初始化两个指针：
- before_head 和 before 用于跟踪小于 x 的节点列表的开始和结束。
- after_head 和 after 用于跟踪大于或等于 x 的节点列表的开始和结束。
遍历原始链表：
- 对于每个节点，如果其值小于 x，则将其添加到 before 列表。否则，将其添加到 after 列表。
结合两个链表：
- 将 before 链表链接到 after_head，以组合两个分区。
- 返回 before_head.next 作为修改后的链表的头节点。

Python 代码实现

Python Code Implementation

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

def partition(head: ListNode, x: int) -> ListNode:
    before_head = ListNode(0)
    before = before_head
    after_head = ListNode(0)
    after = after_head

    while head:
        if head.val < x:
            before.next = head
            before = before.next
        else:
            after.next = head
            after = after.next
        head = head.next

    # Link the end of before list to the beginning of after list
    before.next = after_head.next
    after.next = None

    return before_head.next

复杂度分析

Complexity Analysis

时间复杂度 (Time Complexity): O(N), where N is the number of nodes in the linked list. We traverse the list once.
空间复杂度 (Space Complexity): O(1), since we only use a constant amount of extra space (ignoring the space required for the output).
时间复杂度：O(N)，其中 N 是链表中的节点数。我们遍历链表一次。
空间复杂度：O(1)，因为我们只使用了常量级的额外空间（不包括输出所需的空间）。

总结

Conclusion

By creating two separate linked lists and combining them, we can effectively partition a linked list around a given value while preserving the relative order of nodes within each partition. This approach ensures that the operation is both efficient and easy to implement.

通过创建两个独立的链表并将它们结合在一起，我们可以有效地围绕给定值对链表进行分隔，同时保留每个分区中节点的相对顺序。这种方法确保操作既高效又易于实现。

Post Views: 300

CODEBITWAVE

Algorithms 101: Preserving Relative Position in Linked List