题目

编写程序以x为基准分割链表，使得所有小于x的节点排在大于或者等于x的节点之前。如果链表中包含x，x只需要出现在小于x的元素之后（如下所示）。分割元素x只需要处于“右半部分”即可，其不需要被置于左右两部分之间。

思路

1. 创建两个链表，分别保存左边部分和右边部分。 ```python

   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:

    # 题意：将大于x的元素置于链表右侧；反之置于链表左侧
    left, right = ListNode(0), ListNode(0)
    dummy_left = left
    dummy_right = right
    while head is not None:
        if head.val < x:
            left.next = head
            left = left.next
        else:
            right.next = head
            right = right.next
        head = head.next
    right.next = None
    left.next = dummy_right.next
    return dummy_left.next

2. 定义前后指针pre，cur，cur所指元素小于x，则交换。即可保证pre指针之前所有元素小于x，pre之后元素≥x。
```python
class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        pre, cur = head, head
        while cur:
            if cur.val < x:
                pre.val, cur.val = cur.val, pre.val
                pre = pre.next
            cur = cur.next
        return head

1. 头插法

   # 头插法
   class Solution:
    def partition(self, head: ListNode, x: int) -> ListNode:
        dummy = ListNode(-1, head)
        pre, cur = dummy, head
        while cur:
            if cur.val < x and head != cur:
                pre.next = cur.next
                cur.next = dummy.next
                dummy.next = cur
                cur = pre.next
            else:                                                                                
                pre = pre.next
                cur = cur.next
        return dummy.next