首先题意：链表中数字小于x的值放在左边，数字大于x的值放在右边，且左半部分内部和右半部分内部相对顺序是链表的遍历顺序，保持不变

• 解法1：双指针
• 解法2：定位后分叉，分为左半部分和右半部分

解法1：双指针，需要额外两个头节点

public ListNode partition (ListNode head, int x) {
        // write code here
        if(head == null){
            return head;
        }
        ListNode less = new ListNode(-101);
        ListNode lessBak = less; 
        ListNode more = new ListNode(101);
        ListNode moreBak = more;
        ListNode cur = head;
        while(cur!=null){
            if(cur.val < x){
                less.next = cur;
                less = less.next;
            }else{
                more.next = cur;
                more = more.next;
            }
            cur = cur.next;
        }
        less.next = moreBak.next;
        more.next = null;//至关重要
        return lessBak.next;
}

解法2：定位后分叉，分为左半部分和右半部分

• 搜索定位到第一个分叉点，即第一个大于x的节点，作为右半部分的开头
• 往后遍历，小于x插在左半部分的尾部，大于x插在右半部分的尾部

public ListNode partition (ListNode head, int x) {
        // write code here
        ListNode dummy = new ListNode(-101);
        dummy.next = head;
        ListNode cur = dummy;
        ListNode left,right,rightHead;
        while(cur.next!=null && cur.next.val<x){
            cur = cur.next;
        }
        left = cur;
        right = left.next;
        rightHead = right;
        if(right == null){
            return head;
        }
        ListNode temp = null;
        while(right.next!=null){
            if(right.next.val<x){
                left.next = right.next;
                right.next = right.next.next;
                left.next.next = rightHead;
                left = left.next;
            }else{
                right = right.next;
            }
        }
        right.next = null;
        return dummy.next;
    }