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的值之前，并且要維持原鏈表的順序。
思路：題意相當(dāng)于把鏈表分成兩部分刺啦，小于x的和大于等于x的兩端交排。于是想到可以用兩個新鏈表來記錄這兩段盛撑，最后把小于x那段的尾部和另一段的頭部連結(jié)起來就可以了植阴。
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;
}