Partition List

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.

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;
}

Partition List

原文：http://blog.csdn.net/u014082714/article/details/44308063