值x将链表划分为两部分，小于x的结点排在大于或等于x 的结点之前

编写代码，以给定值x为基准将链表分割为两部分，所有小于x的结点将排在大于或等于x的结点之前。

/*传入链表的首结点，以及作为链表分割基准的值*/
#include<iostream>
using namespace std;
typedef struct node
{
int data;
    struct node* next;
}* LinkedListNode;


LinkedListNode partition(LinkedListNode node, int x)
{
LinkedListNode beforeStart = NULL;
LinkedListNode beforend = NULL;
LinkedListNode afterStart = NULL;
LinkedListNode afterEnd = NULL;
/*分割链表*/
while (node != NULL)
{
LinkedListNode next = node->next;
node->next = NULL;
if (node->data < x)
{
/*将结点插入before链表*/
if (beforeStart == NULL)
{
beforeStart = node;
beforend = beforeStart;
}
else
{
beforend->next = node;
beforend = node;
}
}
else
{
/*将结点插入after链表*/
if (afterStart = NULL)
{
afterStart = node;
afterEnd = afterStart;
}
else
{
afterEnd->next = node;
afterEnd = node;
}
}
node = next;
}//end while
if (beforeStart == NULL)
return afterStart;
//合并before和after链表
beforend->next = afterStart;
return beforeStart;
}

/*传入链表的首结点，以及作为链表分割基准的值*/
#include<iostream>
using namespace std;
typedef struct node
{
int data;
struct node* next;
}*LinkedListNode;
LinkedListNode partition(LinkedListNode node, int x)
{
LinkedListNode beforeStart = NULL;
LinkedListNode afterStart = NULL;
/*分割链表*/
while (node != NULL)
{
LinkedListNode next = node->next;
node->next = NULL;
if (node->data < x)
{
/*将结点插入before链表的前端*/
node->next=beforeStart;
beforeStart = node;
}
else
{
/*将结点插入after链表*/
   node->next=afterStart;
afterStart=node;
}
node = next;
}//end while
if (beforeStart == NULL)
return afterStart;
//合并before和after链表
while (beforeStart->next != NULL)
{
beforeStart = beforeStart->next;
}
beforeStart->next = afterStart;
return beforeStart;
}

值x将链表划分为两部分，小于x的结点排在大于或等于x 的结点之前

原文：http://blog.csdn.net/wangfengfan1/article/details/47754049