已知题目要求将小于 x 的值与其他值分开并且前后顺序不能发生改变,那么我们可以创建一个栈,将所有小于 x 的值存放在栈中,然后将栈中的元素一一取出,并采用头插法重新插入链表中. 
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 val) {
        if(pHead == null) return null;
        Stack<Integer> stack = new Stack<>();
        
        ListNode cur = pHead;
        ListNode prev = null;
        while(cur!=null) {
            if(cur.val < val) {
                stack.add(cur.val);
                if(cur == pHead) {
                    pHead = pHead.next;
                    cur = pHead;
                }else {
                    cur = cur.next;
                    prev.next = cur;
                }
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        while(!stack.isEmpty()) {
            ListNode newNode = new ListNode(stack.pop());
            newNode.next = pHead;
            pHead = newNode;
        }
        return pHead;
    }
}