题解 | #链表分割#

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 || pHead.next == null){
            return pHead;
        }
        ListNode minXF = null;
        ListNode minXE = null;
        ListNode maxXF = null;
        ListNode maxXE = null;
        while (pHead != null) {
            if (pHead.val < x) {
                if (minXF == null) {
                    minXE = pHead;
                    minXF = pHead;
                }else {
                    minXE.next = pHead;
                    minXE = pHead;
                }
            }else {
                if (maxXF == null) {
                    maxXE = pHead;
                    maxXF = pHead;
                }else {
                    maxXE.next = pHead;
                    maxXE = pHead;
                }
            }
            pHead = pHead.next;
        }
        if (minXF != null){
            minXE.next = maxXF;
        }
        if (maxXE != null) {
            maxXE.next = null;
        }
        if (minXF == null){
            return maxXF;
        }
        return minXF;
    }
}