Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal tox.
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.
思路：类似于快速排序，由于要求不改变原来的相对顺序，这里必须有节点的交换，要不然直接不交换节点而是之间交换节点内部的值即可。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef struct list_node List;
struct list_node
{
struct list_node* next;
int value;
};
void print_list(List* list)
{
List* tmp=list;
while(tmp != NULL)
{
cout<<tmp->value<<endl;
tmp = tmp->next;
}
}
/*
初始化List 将从1~n的数字插入到链表中
*/
void Init_List(List*& head,int* array,int n)
{
head = NULL;
List* tmp;
List* record;
for(int i=1;i<=n;i++)
{
tmp = new List;
tmp->next = NULL;
tmp->value = array[i-1];
if(head == NULL)
{
head = tmp;
record = head;
}
else
{
record->next = tmp;
record = tmp;
}
}
}
int Len_list(List* list)
{
if(list == NULL)
return 0;
else
return Len_list(list->next)+1;
}
/*类似于快速排序的分割*/
void PartitionList(List*& list,int key)
{
if(list == NULL)
return ;
List* record,*cur,*pre,*tmp;
record = NULL;
cur = list;
pre = NULL;
while(cur != NULL)
{
if(cur->value < key) //插入到pre之后 注意区分第一个的情况
{
tmp = cur->next;
if(pre == NULL)
pre = cur;
if(record == NULL)
{
record = list;
list = cur;
cur->next = record;
record = cur;
pre->next = tmp;
}
else
{
if(pre != record)
{
cur->next = record->next;
record->next = cur;
pre->next = tmp;
record = cur;
}
else
record = pre = cur;
}
cur = tmp;
}
else //
{
pre = cur;
cur = cur->next;
}
}
}
int main()
{
int array[]={5,1,2,7,8,4,3,6,10,9};
//int array[]={1,4,3,2,5,2};
List* list;
Init_List(list,array,sizeof(array)/sizeof(int));
PartitionList(list,5);
print_list(list);
return 0;
}原文：http://blog.csdn.net/yusiguyuan/article/details/44871119