Java链表分割

题目：现有一链表的头指针 ListNode pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。*
链表分割

• 1.分析
• 2.具体步骤
• 3.代码

1. 首先将链表分为前后两段，分割前，分割后
2. 定义4个引用

        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;

3. 定义cur指向头结点
4. 当cur不为空，就比较cur.val和k的值，如果小于k，就放在第一段，如果大于k,就放在第二段
5. 在每一段第一次放入的时候，直接放入就行了，然后cur=cur.next;
6. 在每一段不是第一次插入的时候，采用尾插法，be.next = cur;be = be.next;或者ae.next = cur; ae = ae.next;然后cur=cur.next;
7. 第一段可能没数据，直接返回后半段；还有就是原来链表最后一个数据小于k,那么它应该插在第一段结尾，那么新链表结尾ae.next!=null,那么要手动置空。
8. 最后返回bs

k=15

//链表分割
    public ListNode partition(int x) {
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = this.head;
        while (cur != null) {
            if (cur.val < x) {
                //第一次
                if (bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    //不是第一次，尾插法
                    be.next = cur;
                    be = be.next;
                }
            } else {
                if (as == null) {
                    as = cur;
                    ae = cur;
                } else {
                    //不是第一次
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //预防第一段为空
        if (bs == null) {
            return as;
        }
        be.next = as;

        //预防第二段最后一个节点不为空
        if (as != null) {
            ae.next = null;
        }
        return bs;
    }

测试：

  public static void main(String[] args) {
        MylinkedList mylinkedList1 = new MylinkedList();
        mylinkedList1.addLast(12);
        mylinkedList1.addLast(3);
        mylinkedList1.addLast(34);
        mylinkedList1.addLast(5);
        mylinkedList1.addLast(56);

        ListNode ret=mylinkedList1.partition(15);
        mylinkedList1.display2(ret);
    }