/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param x int整型 
     * @return ListNode类
     */
    public ListNode partition (ListNode head, int x) {
        // write code here
        //先找到x节点
        //然后利用双指针
        ListNode left = new ListNode(0);
        left.next = head;
        ListNode temp = left;
        while(left.next != null && left.next.val < x){
            left = left.next;
        }
        //上面已经找到了x节点左边第一个节点了
        //插入的节点
        ListNode next = left.next;
        //寻找需要向前移动到左边的节点
        ListNode right = next;
        while(right != null && right.next != null){
            if(right.next.val < x){
                //小于那就需要移动到left那边，并且保证节点顺序不变
                left.next = right.next;
                right.next = right.next.next;
                left.next.next = next;
                left = left.next;
            }else{
                right = right.next;
            }
        }
        return temp.next;
    }
}