86. Partition List 按值调整链表为两部分

将链表的数据按照值的大小拆分为左右两部分，有一种解法是扫描一遍链表，将数据分别放入两个数组中，然后再扫描一次原链表，更新链表的值。

下面这种是直接一遍扫描完成。

# 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:
        if head is None or head.next is None:
            return head
        left_dummy = ListNode()
        right_dummy = ListNode()
        left_cur = left_dummy
        right_cur = right_dummy
        pivot = head
        while pivot:
            if pivot.val < x:
                left_cur.next = pivot
                left_cur = left_cur.next
                pivot = pivot.next
                left_cur.next = None
            else:
                right_cur.next = pivot
                right_cur = right_cur.next
                pivot = pivot.next
                right_cur.next = None
        left_cur.next = right_dummy.next
        return left_dummy.next