题解 | 链表分割

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) {
        // write code here
        ListNode cur = pHead;
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        if(pHead == null) return null;
        while(cur != null)
        {
            if(cur.val < x)
            {
                if(bs == null)
                {
                    bs = be = cur;
                }else{
                    be.next = cur;
                    be = be.next;
                }
            }else{
                if(as == null)
                {
                    as = 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;
    }
}

定义两个区间 bs be as ae，分别根据与x的大小关系，用cur遍历原链表往区间里面放元素，然后最后把两个区间拼接起来。如果ab区间内均有元素，就会存在最后一个元素的原指针可能不为Null的情况，需要手动调整。如果a或者b任一区间的元素不存在，全部都在另一区间，就说明顺序并未改变，最后一个指针一定指向Null。