题解 | 链表分割

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) {
        ListNode newhead = new ListNode(0);//创建头节点
        newhead.next=pHead;
        ListNode low = newhead;
        ListNode big = newhead;
        while(big!=null && big.next!=null){
            if(big.next.val <x ){
                if(big==low){
                    big=big.next;
                    low=low.next;
                }
                else {
                    ListNode cur = big.next;//保存要移动的节点
                    big.next = big.next.next;//将该节点移出
                    //将该节点插入
                    cur.next = low.next;
                    low.next = cur;
                    low = low.next; //将小节点更新
                }
            }
            else{
                big = big.next;
            }
        }
        return newhead.next;
    }
}