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.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->3->4->5.
题意：有一个无序的链表，给了一个值x，要把链表中小于x的值排列在大于等于x的值之前，并且要维持原链表的顺序。
思路：题意相当于把链表分成两部分，小于x的和大于等于x的两端。于是想到可以用两个新链表来记录这两段，最后把小于x那段的尾部和另一段的头部连结起来就可以了。
public ListNode partition(ListNode head, int x) {
if (head == null || head.next == null) {
return head;
}
ListNode left = new ListNode(0);
ListNode leftRoot = left;
ListNode right = new ListNode(0);
ListNode rightRoot = right;
ListNode dummy = head;
while (dummy != null) {
if (dummy.val < x) {
left.next = dummy;
left = left.next;
} else {
right.next = dummy;
right = right.next;
}
dummy = dummy.next;
}
left.next = null;
right.next = null;
left.next = rightRoot.next;
return leftRoot.next;
}