題目:
給定一個單連結清單和數值x,劃分連結清單使得所有小于x的節點排在大于等于x的節點之前。
你應該保留兩部分内連結清單節點原有的相對順序。
樣例:
給定連結清單 1->4->3->2->5->2->null,并且 x=3
傳回 1->2->2->4->3->5->null
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param head: The first node of linked list.
* @param x: an integer
* @return: a ListNode
*/
ListNode *partition(ListNode *head, int x) {
// write your code here
if(head==NULL) return NULL;
ListNode *dummy=new ListNode();
dummy->next=head;
ListNode *temp=head;
//如果要插入第一個位置的話,那麼dummy結點可以幫助我們
//避免pretemp是空結點而導緻無法插入的錯誤。
ListNode *pretemp=dummy;
ListNode *cur=NULL;
ListNode *precur=NULL;
//找到第一個大于等于x的值作為分界線,存在temp中。
while(temp!=NULL&&temp->val<x)
{
pretemp=temp;
temp=temp->next;
}
if(temp!=NULL&&temp->next!=NULL)
{
precur=temp;
cur=temp->next;
}
//找到分界線右側小于x的值的結點,将其存在cur中。
while(cur!=NULL)
{
while(cur!=NULL&&cur->val>=x)
{
precur=cur;
cur=cur->next;
}
//如果找到的話将其插入到分界線以前的第一個位置
if(cur!=NULL)
{
precur->next=cur->next;
cur->next=temp;
pretemp->next=cur;
pretemp=cur;
cur=precur->next;
}
}
temp=dummy;
dummy=dummy->next;
free(temp);
return dummy;
}
};