题解 | 链表分割

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
        if(pHead==null){
            return null;
        }
        ListNode head=new ListNode(0);
        head.next=pHead;
        ListNode pre=head;
        ListNode precur;
        while(pre!=null&&pre.next!=null&&pre.next.val<x){
            
            pre=pre.next;//此时pre是在大于等于x的前一个节点
        }

        precur=pre.next;//cur前一个节点（变）
        ListNode large=precur;//记录第一个大于x的节点（不变）
        while(precur!=null&&precur.next!=null){
            ListNode cur=precur.next;
            if(cur.val<x){
                //插入pre后面
                precur.next=cur.next;
                cur.next=large;
                pre.next=cur;
                pre=cur;
            }else{
                precur=precur.next;
            }
        
        }

        return head.next;//我一开始写的是pHead,但是因为pHead也就是头结点（有值）可能发生变化，比如第一个数就大于x，后面有数需要插入到第一个节点之前，这样就不是头结点了。所以应该返回自己设置的空头结点的下一个节点
    }
}