題目
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.
分析
給定一個(gè)鏈表禽炬，要求將小于x的數(shù)字移到大于或等于x的節(jié)點(diǎn)之前。那么首先找到那個(gè)分界點(diǎn)攀涵，然后再講之后小于x的點(diǎn)移到該分界點(diǎn)之后曙蒸。直到所有的節(jié)點(diǎn)都已經(jīng)處理衫哥。需要注意首節(jié)點(diǎn)的特殊情況處理。
/**
* 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;
}
