Leetcode 86

Question

Solution

创建一个随意的结点，为了防止head的首元素就大于x的情况。

创建两个指针，pre和cur。首先需要找到第一个大于等于x的结点，将pre指向其前面的一个结点。cur从pre的位置开始，往下遍历。如果出现某个结点的val小于x，则将其添加到pre后，pre后移一位。否则cur一直往后移动。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        if not head:
            return 
        ans = pre = cur = ListNode(0)
        ans.next = head
        while pre.next:
            if pre.next.val < x:
                pre = pre.next
            else:
                break
        cur = pre
        while cur.next:
            if cur.next.val >= x:
                cur = cur.next
            else:
                target = cur.next
                cur.next = target.next
                target.next = pre.next
                pre.next = target
                pre = pre.next
        return ans.next