Java链表分割

描述

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

思路：

我们把小于原来链表小于x的放在一个链表里，把大于等于x的元素放在另外一个链表里，最后连接即可，图像描述：

//定义类
public class Solution {
    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode Solution(ListNode pHead, int x) {
        // write code here
        ListNode cur = pHead;
        ListNode bs, be, as, ae;//上张图片有说明具体变量含义
        be=bs=as=ae=null;
        if (pHead == null)return null;
        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;//如果小于x的区域没有值，bs=null，那么后面ba.next会报错
        if (as != null)ae.next = null;//如果初始序列的最后一个值放在了小于x的区间，
        // 这时候大于x的区间的最后一个值的next的值不是null,我们最后的返回结果将无法停止
        be.next = as;
        return bs;
    }
}