思路

主要思路是创建两个链表，一个保存值小于x的元素，另一个保存值大于等于x的元素。最后进行合并

算法

code

public ListNode partition(ListNode head, int x) {
        //设立两个虚拟头结点 分别保存比x小的元素和比x大的元素
        ListNode before_head = new ListNode(-1);
        ListNode after_head = new ListNode(-1);
        ListNode before = before_head;
        ListNode after = after_head;
        while(head!=null){
            if(head.val<x){          //如果遇到比x小的元素
                before.next = head;
                before = before.next;
            }else{
                after.next = head;
                after = after.next;
            }
            head = head.next;
        }
        after.next = null;         //后面部分的尾部设为null     
        before.next = after_head.next;    //连接上两个链表  
        return before_head.next;   //返回第一部分的虚拟头结点的next
}