题解 | #链表分割#

import java.util.*;

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

    ListNode(int val) {
        this.val = val;
    }
    将链表分割为两个，定义四个节点 bs，be，as，ae分别表示两段链表的头和尾
    本题可以采用，将小于x的节点头插到前面一段链表中,大于的放在后一段。但是需要考虑是否存在大于x的节点和小于x的节点。
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;

        ListNode cur = pHead;
        while (cur != null) {
		  //小于插到前一段
            if(cur.val < x) {
			  //为空时，为bs、be赋值指向cur。
                if(bs == null) {
                    bs = cur;
                    be = cur;
                }else {
				  //不为空时插入be后面
                    be.next = cur;
                    be = be.next;
                }
			  //大于插入后一段
            }else {  
			为空时，为as、ae赋值指向cur。
                if(as == null) {
                    as = cur;
                    ae = cur;
                }else {
				  //插入ae后面
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        // 有可能不会同时存在小于x 和 大于等于x 的数据
	  //不存在小于的时候，不能直接 be.next = as;
        if(bs == null) {
            return as;
        }
        //第一段不为空，连接起来（第二段为空不影响）
        be.next = as;
        //第2个段为空不为空的问题，加if判断为不为空，不能1直接将ae.next置空以免空指针异常
        if(as != null) {
            ae.next = null;
        }
        return bs;
        
    }
}