#LC 86.py

#LC 86.py 分割链表

# 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]:
        # 存放小于 x 的链表的虚拟头结点
        dummy1 = ListNode(-1)
    # 存放大于等于 x 的链表的虚拟头结点
        dummy2 = ListNode(-1)
    # p1, p2 指针负责生成结果链表
        p1, p2 = dummy1, dummy2
    # p 负责遍历原链表，类似合并两个有序链表的逻辑
    # 这里是将一个链表分解成两个链表
        p = head
        while p:
            if p.val >= x:
                p2.next = p
                p2 = p2.next
            else:
                p1.next = p
                p1 = p1.next
        # 不能直接让 p 指针前进，
        # p = p.next
        # 断开原链表中的每个节点的 next 指针
            temp = p.next
            p.next = None
            p = temp

    # 连接两个链表
        p1.next = dummy2.next

        return dummy1.next
    # https://labuladong.online/algo/essential-technique/linked-list-skills-summary-2/#div_partition-list