86. Partition List
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal tox.
You should preserve the original relative order of the nodes in each of the two partitions.
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
//使用两个队列，一个存储小于x的，一个存储大于等于x的，然后连接两个队列
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode dummy1 = new ListNode(0);
ListNode dummy2 = new ListNode(0);
ListNode curr1 = dummy1;
ListNode curr2 = dummy2;
while (head != null) {
if (head.val < x) {
curr1.next = head;
curr1 = head;
} else {
curr2.next = head;
curr2 = head;
}
head = head.next;
}
curr2.next = null;//一定要有这句话，比如 5->6->1->2, x=3，c1：1->2,c2：5->6，我们让2指向5了，如果还有这句话，会保持6->1，会形成个cycle
curr1.next = dummy2.next;
return dummy1.next;
}
}
