86. Partition List

Leetcode: https://leetcode.com/problems/partition-list/

看似是 quick sort，但因为linked list 的结构，没法从两头遍历。

• 只能是双指针初始化在同一边，右指针遍历，遇到<x 的元素就插入到左指针后面，并在原地删除，左指针同步往右移动一格（保持相对顺序）。

• 需要依靠 dummy head 来解决操作 head node 的问题。

• 注意左指针不能超过右指针，超过了就要移动右指针。

• 注意异地插入并且原地删除的操作。

# 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:
        dummy = ListNode()
        dummy.next = head
        i, j = dummy, dummy
        while j and j.next:
            while j.next and j.next != i and j.next.val < x:
                node = j.next
                j.next = j.next.next
                following = i.next
                i.next = node
                node.next = following
                i = i.next
            j = j.next
        return dummy.next