题目

给你一个链表的头节点 head 和一个特定值 x，请你对链表进行分隔，使得所有 小于 x 的节点都呈现在 大于或等于 x 的节点之前。

你该当 保留 两个分区中每个节点的初始绝对地位。

输出：head = [1,4,3,2,5,2], x = 3
输入：[1,2,2,4,3,5]

输出：head = [2,1], x = 2
输入：[1,2]

一开始题目都没读懂 …
其实题目的意思就是：比方示例中的数组，小于 3 的都放到后面，大于等于 3 的都放到前面，并且不扭转绝对程序。

思路

保护两个链表：大链表、小链表
大链表用来寄存大于等于 x 的局部
小链表用来寄存小于 x 的局部
最初将小链表和大链表拼接起来，就是最终答案

def partition(head: ListNode, x: int) -> ListNode:
    bigHead, smallHead = ListNode(-1), ListNode(-1)
    bigTail,smallTail = bigHead,smallHead

    while head:
        if head.val < x:
            smallTail.next = head
            smallTail = smallTail.next
        else:
            bigTail.next = head
            bigTail = bigTail.next
        head = head.next

    smallTail.next = bigHead.next
    bigTail.next = None
    return smallHead.next