思路：创建两个链表分别存储小于x 的和大于x的节点，再将两个链表拼接即可。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        if(head==null) return null;
        // 如果直接交换，节点相对位置就变了
        // 创建新哨兵
        ListNode newHeadSmall = new ListNode(0);
        ListNode newHeadBig = new ListNode(0);
        ListNode p = newHeadSmall;
        ListNode q = newHeadBig;
        while(head!=null){
            if(head.val<x){
                p.next = new ListNode(head.val);
                p.next.next = null;
                p = p.next;
            }else{
                q.next = new ListNode(head.val);
                q.next.next = null;
                q = q.next;
            }
            head = head.next;
        }
        p.next = newHeadBig.next;
        q.next = null;
        return newHeadSmall.next;
    }
}