题解 | #链表分割#

public class Partition {
    public ListNode partition(ListNode head, int x) {
        //1. 创建五个指针
        //创建两个傀儡节点 newhead1 和 newhead2
        //再创建这两个傀儡节点的替身，cur1，和 cur2
        //创建一个指针 sign 用来遍历原来的链表
        ListNode newhead1 = new ListNode(-1);
        ListNode newhead2 = new ListNode(-2);
        ListNode cur1 = newhead1;
        ListNode cur2 = newhead2;
        ListNode sign = head;
        //2. 进行区间划分
        //比 x 值小的放在前一个区间比 x 值大的放在后一个区间
        while(sign != null){
            if(sign.val < x){
                cur1.next = sign;
                cur1 = cur1.next;
                sign = sign.next;
            }else{
                cur2.next = sign;
                cur2 = cur2.next;
                sign = sign.next;
            }
        }
        //3. 傀儡节点失效，重新定义两个区间的头结点
        newhead1 = newhead1.next;
        newhead2 = newhead2.next;
        //4. 连接两个区间
        cur1.next = newhead2;
        //5. 考虑特殊情况
        if(newhead2 != null){
            cur2.next = null;
        }
        if(newhead1 == null  ){
            return newhead2;
        }
        return newhead1;
    }
}