1. Description

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.

2. Example

Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

3. Code

public class LeetCode0086 {

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public ListNode partition(ListNode head, int x) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        dummy.next = head;
        ListNode record = dummy;
        ListNode pre = dummy;
        ListNode p = head;
        while (p != null) {
            if (p.val < x) {
                if (record != pre) {
                    pre.next = p.next;
                    p.next = record.next;
                    record.next = p;
                    record = p;
                    p = pre.next;
                } else {
                    pre = p;
                    p = p.next;
                    record = pre;
                }

            } else {
                pre = p;
                p = p.next;
            }
        }
        return dummy.next;
    }
}