题目

方法

将原来的Linked List 拆分成两个， 一个记录比X小的元素，另一个记录比X大的元素，最后将其合并。

    public ListNode partition(ListNode head, int x) {
        ListNode lessStart = null;
        ListNode lessEnd = null;
        ListNode greaterStart = null;
        ListNode greaterEnd = null;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val < x) {
                if (lessStart == null) {
                    lessStart = cur;
                    lessEnd = cur;
                } else {
                    lessEnd.next = cur;
                    lessEnd = cur;
                }
            } else {
                if (greaterStart == null) {
                    greaterStart = cur;
                    greaterEnd = cur;
                } else {
                    greaterEnd.next = cur;
                    greaterEnd = cur;
                }
            }
            cur = cur.next;
        }
        if (lessStart == null) {
            return greaterStart;
        }
        if (greaterStart == null) {
            return lessStart;
        }
        greaterEnd.next = null;
        lessEnd.next = greaterStart;
        return lessStart;
    }