subject ： Give you a list of the head node head And a specific value x , Please separate the linked list , Make all Less than x All of the nodes appear in Greater than or equal to x Before the node . You should Retain The initial relative position of each node in the two partitions .
Example 1：
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]
Tips ：
The number of nodes in the linked list is in the range [0, 200] Inside
-100 <= Node.val <= 100
-200 <= x <= 200
Program description ：
Create two dummy nodes , One is for storing ratio x Small number , A storage is greater than or equal to x Number of numbers , Then merge the two linked lists .（ Suggest drawing to understand ）
All the code ：
# 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: ListNode, x: int) -> ListNode:
p = ListNode(0)
small = p
q = ListNode(0)
big = q
while head:
if head.val<x:
small.next = head
small = small.next
else:
big.next = head
big = big.next
head = head.next
big.next = None
small.next = q.next
return p.next
Title source ： Power button （leetcode）
