学步园

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.

<span style="font-size:18px;">typedef struct Node
{
int data;
    struct Node *next;

}Node,*LinkList;

void PartitionList(LinkList *L,int x)
{
     LinkList left=(LinkList)malloc(sizeof(Node));
     LinkList right=(LinkList)malloc(sizeof(Node));
     LinkList p=left;
     LinkList q=right;
     Node* curr=*L;
     curr=curr->next;
     while(curr)
     {
         if(curr->data<x)
         {
             p->next=curr;
             p=curr;
            //p->next=NULL;
          }
         else
        {
            q->next=curr;
            q=curr;
           //q->next=curr;q可能是最后一个指向NULL，如果再->next可能会出错
         }
        curr=curr->next;
     }
     p->next=right->next; 
     *L=left;
}</span>