题解 | 链表分割

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 lowh = null;//小头节点
        ListNode lowa = null;//小尾节点
        ListNode bigh = null;//大头节点
        ListNode biga = null;//大尾节点
        while(pHead!=null){
           if(pHead.val < x){
               //如果小头节点为空
               if(lowh == null){
                   lowh = lowa = pHead;
               }
               else{
                   lowa.next = pHead;
                   lowa = lowa.next;
               }
           }
           else{
               //如果大头节点为空
               if(bigh == null){
                   bigh = biga = pHead;
               }else{
                   biga.next = pHead;
                   biga = biga.next; 
               }
           }
           pHead = pHead.next;
        }
        //如果小链表为空
        if(lowh==null){
            return bigh;//返回大链表
        }
        lowa.next=bigh;//将两个链表合并
        //如果大链表不为空
        if(bigh!=null){
            biga.next=null;//将链表尾部的下一个节点置为空
        }
        return lowh;
    }
}