Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Have you met this question in a real interview?

Yes

Example

Given1->4->3->2->5->2->nulland x =3,
return1->2->2->4->3->5->null.

1. quick sort list partition step

public class Solution {
    /**
     * @param head: The first node of linked list.
     * @param x: an integer
     * @return: a ListNode 
     */
    public ListNode partition(ListNode head, int x) {
        // write your code here
        if (head == null) {
            return head;
        }

        ListNode leftDummy = new ListNode(0);
        ListNode rightDummy = new ListNode(0);
        ListNode leftHead = leftDummy;
        ListNode rightHead = rightDummy;

        leftHead.next = head;
        rightHead.next = head;

        while (head != null) {
            if (head.val < x) {
                leftHead.next = head;
                leftHead = leftHead.next;
            } else {
                rightHead.next = head;
                rightHead = rightHead.next;
            }

            head = head.next;
        }

        leftHead.next = null;
        rightHead.next = null;

        leftHead.next = rightDummy.next;
        return leftDummy.next;
    }
}