from utils.list_utils import ListNode, create_link_list, print_link_list


class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        if head is None:
            return head

        rlt=p1=ListNode(0)
        p1.next=head  # 指向最后一个小于x的值
        p2=p1.next  # 指向正在处理的值
        p2p=p1  # 正在处理的值的前一位

        while p2!=None:
            if p2.val<x:  # 当正在处理的值小于x时
                if p2p!=p1:  # 对于当前处理值不是最后一个小于x值的后一位
                    # 移除小值
                    p2p.next=p2.next
                    p3=p2
                    p2=p2p.next
                    # 将小值前置
                    p3.next=p1.next
                    p1.next=p3
                    p1=p3
                else:  # 对于当前处理值是最后一个小于x值的后一位，只需要移动指针即可
                    p1=p1.next
                    p2p=p2
                    p2=p2.next
            else:
                p2p=p2
                p2=p2.next

        return rlt.next

sol=Solution()
rlt=sol.partition(create_link_list([1,4,3,2,5,2]),3)
print_link_list(rlt)
rlt=sol.partition(create_link_list([2,1]),2)
print_link_list(rlt)
rlt=sol.partition(create_link_list([1]),0)
print_link_list(rlt)
rlt=sol.partition(create_link_list([1,2,3]),4)
print_link_list(rlt)