题解 | #链表分割#

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) {
        //比x小，bs and he为前链表的头和尾
       ListNode bs=null;
       ListNode be=null;
       //比x大， as and ae...
       ListNode as=null;
       ListNode ae=null;
       //定义新的头，防止phead指针移动，影响其他使用操作
       ListNode head=pHead;
       //遍历链表
       while(head!=null){
        //比x小，存前链表中
        if(head.val<x){
            if(bs==null){
                bs=be=head;
                head=head.next;
            }else{
                be.next=head;
                be=be.next;
                head=head.next;
            }
        }else{      //比X大
            if(as==null){
                as=ae=head;
                head=head.next;
            }else{
                ae.next=head;
                ae=ae.next;
                head=head.next;
            }
        }
       }
       //bs=null,前链表为空
        if(bs==null){
            return as;
        }
        //as=null,后链表为空，走到这里，前链表不可能为空
        if(as==null){
            be.next=as;//最后节点next置空
            return bs;
        }
        //走到这里，前后链表都不为空，连接两个链表尾头，这里后链表的尾可能不为空，进行判断！！！
        if(ae.next!=null){
            ae.next=null;
        }
        be.next=as;
        return bs;
    }
}