1.new 两个新链表用来进行关于x的划分，以及相对位置不变；
2.遍历给定链表，进行划分；
注意：
（1）如何进行结点插入/新链表合并 ？---因为尾插效率低，所以我们使用标记，随着插入进行标记，而合并也会因为标记变得更简单
（2）如何设置标记？---首先我们分别对两个新链表设置标记变量，但由于空链表指向next是非法的，所以我们一开始会在两个新链表中各加入一个结点
（3）注意合并时候要忽略无意义结点(一开始的结点)，以及注意第2个链表的最后一个结点要指向空 
import java.util.*;

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        
        if(pHead==null){
            return pHead;
        }
        
        //1.先new两个链表，方便后续使用
        ListNode head1 = new ListNode(0);  //保证链表1不为空--可以指向next
        ListNode head2 = new ListNode(0);  //保证链表2不为空--可以指向next
        
        ListNode flag1 = head1;  //一开始标记链表一的头结点
        ListNode flag2 = head2;  //一开始标记链表二的头结点
        
        //2.判断给定链表中的结点val与x之间的关系
        ListNode cur = pHead;
        while(cur!=null){
            if(cur.val < x){
                flag1.next=cur;
                flag1=flag1.next;
            }else{
                flag2.next=cur;
                flag2=flag2.next;
            }
            cur=cur.next;
        }
        
        //3.开始进行善后及合并两个新链表
        //3.1.善后
        flag2.next=null;  //把链表2最后一个结点的next置空，防止出现与其他结点相连的状况
        //3.2.合并两个新链表
        flag1.next=head2.next;  //注意把一开始的无意义结点剔除
        
        return head1.next;
    }
}