Write code to partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x. lf x is contained within the list, the values of x only need to be after the elements less than x (see below). The partition element x can appear anywhere in the "right partition"; it does not need to appear between the left and right partitions.
EXAMPLE
Input: 3 -> 5 -> 8 -> 5 -> 10 -> 2 -> 1 [partition = 5]
Output: 3 -> 1 -> 2 -> 10 -> 5 -> 5 -> 8

Hint

• There are many solutions to this problem, most of which are equally optimal in runtime. Some have shorter, cleaner code than others. Can you brainstorm different solutions?
• Consider that the elements don't have to stay in the same relative order. We only need to ensure that elements less than the pivot must be before elements greater than the pivot. Does that help you come up with more solutions?

Solution

本题要求以 x 为参考对一个链表进行划分，将比小于 x 的结点全部移动到大于等于 x 结点的前面，Leetcode中有原题但是有额外的条件，需要保持各元素相对位置，本题中可以不考虑。但是笔者对原题中例子的输出表示疑问，不知是否为印刷错误还是有对应的解法，我能得到的一个近似解为 3 -> 1 -> 2 -> 5 -> 8 -> 5 -> 10，如果有同学知道例子中的解法还望留言告知啦。
首先考虑维持相对位置的一个解法，设置两个空链表 left 和 right，然后遍历原链表，当遇到比小于 x 的结点时插入 left，反之插入 right，最后连接 left 和 right 即可。

public ListNode partition(ListNode head, int x) {
    if (head == null) return head;
    ListNode lHead = new ListNode(-1), rHead = new ListNode(-1);
    ListNode left = lHead, right = rHead;
    while (head != null) {
        if (head.val < x) {
            left.next = head;
            left = left.next;
        } else {
            right.next = head;
            right = right.next;
        }
        head = head.next;
    }
    right.next = null;
    left.next = rHead.next;
    return lHead.next;
}

然后是不考虑相对顺序的情况，方法类似，只不过每次插入时采用头插法，省略了自己建立空链表的步骤。

public static ListNode partition(ListNode head, int x) {
    ListNode left = head, right = head;
    while (head != null) {
        ListNode next = head.next;
        if (head.val < x) {
            head.next = left;
            left = head;
        } else {
            right.next = head;
            right = head;
        }
        head = next;
    }
    right.next = null;
    return left;
}