public class parition2_4 {

    public static void main(String[] args) {
        //测试
    //    int [] arr={1,3,4,8,2,6,7};
        int [] arr={1,3,4,6,7,1,3};
        ListNode head=new ListNode(0);
        ListNode p=head;
        //构造链表
        for (int i = 0; i < arr.length; i++) {
            p.next=new ListNode(arr[i]);
            p=p.next;
        }
        System.out.println();
        System.out.println("before:"+head.toString());
        patitionNode(head,4);
        System.out.println("after :"+head.toString());

    }

    private static ListNode patitionNode(ListNode head, int x) {
        ListNode p=head;
        ListNode leftHead=null;
        ListNode leftTail=null;
        ListNode rightHead=null;
        ListNode rightTail=null;
        while(p!=null){
            int pValue=p.value;
            if(pValue <x){//大于基准值，放到右边
                if(leftTail==null){
                    leftHead=p;
                    leftTail=p;
                }else{
                    leftTail.next=p;
                    leftTail=leftTail.next;
                }
            }else{
                if(rightTail==null){
                    rightHead=p;
                    rightTail=p;
                }else{
                    rightTail.next=p;
                    rightTail=rightTail.next;
                }
            }
            
            p=p.next;
            
        }
        
        if(leftHead==null){
            return rightHead;
        }
        leftTail.next=rightHead;
        if(rightTail!=null){
            rightTail.next=null;
        }
        return leftHead;
    }

}