题目：
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.
分析：链表的特点在于不存在固定大小的存储区域，节点可以任意移动，插入。算法：遍历链表，分别插入两个新链表，一个小于x，一个大于等于x。然后把后者拼接在前者之后。
ListNode *partition(ListNode *head, int x) {
if(!head||!head->next) return head;
ListNode dummy_left(-1),dummy_right(-1);
ListNode *cur_left = &dummy_left, *cur_right = &dummy_right;
while(head)
{
if(head->val<x)
{
cur_left->next=head;
cur_left=head;
}
else
{
cur_right->next=head;
cur_right=head;
}
head=head->next;
}
cur_left->next=dummy_right.next;
cur_right->next= NULL;
return dummy_left.next;
}
