题目
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->4->3->5.
分析
给定一个链表，要求将小于x的数字移到大于或等于x的节点之前。那么首先找到那个分界点，然后再讲之后小于x的点移到该分界点之后。直到所有的节点都已经处理。需要注意首节点的特殊情况处理。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* partition(struct ListNode* head, int x) {
struct ListNode *p1=head,*p2=head,*temp=head;
bool firstnode=true;
while(p1!=NULL)
{
if(p1->val>=x)
break;
p2=p1;
p1=p1->next;
}
if(p1!=head)
firstnode=false;
if(p1==NULL)
return head;
while(p1->next!=NULL)
{
if(p1->next->val<x)
{
if(firstnode==true)
{
temp=p1->next->next;
head=p1->next;
head->next=p2;
p1->next=temp;
p2=head;
firstnode=false;
}
else
{
temp=p1->next->next;
p1->next->next=p2->next;
p2->next=p1->next;
p1->next=temp;
p2=p2->next;
}
}
else p1=p1->next;
}
return head;
}
