算法：分区列表86. Partition List-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法：分区列表86. Partition List。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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 1:
算法：分区列表86. Partition List

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

Example 2:

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

Constraints:

The number of nodes in the list is in the range [0, 200].
-100 <= Node.val <= 100
-200 <= x <= 200

双链表解法

Solution
The problem wants us to reform the linked list structure, such that the
elements lesser that a certain value x, come before the elements greater or
equal to x. This essentially means in this reformed list, there would be a
point in the linked list before which all the elements would be smaller than
x and after which all the elements would be greater or equal to x.
Let’s call this point as the JOINT.
算法：分区列表86. Partition List
Reverse engineering the question tells us that if we break the reformed list
at the JOINT, we will get two smaller linked lists, one with lesser elements
and the other with elements greater or equal to x. In the solution, our main aim
is to create these two linked lists and join them.文章来源地址https://www.toymoban.com/news/detail-501175.html

# 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]:
        before = before_head = ListNode(0)
        after = after_head = ListNode(0)
        while head:
            if head.val < x:
                before.next = head
                before = before.next
            else:
                after.next = head
                after = after.next
            head = head.next
        
        after.next = None
        before.next = after_head.next
        return before_head.next