你参考一下这些链表排序，希望对你的解题有所帮助：
请看ListSort3(L);
程序初始顺序是：6 3 67 2 15 13 10 6 4
排好序的顺序是：3 2 4 6 6 67 15 13 10
#include<stdio.h>
#include <stdlib.h>
#include <math.h>
/************************************************************************/
/* 常量定义 */
/************************************************************************/
#define ElemType int
#define Status int
#define TRUE 1
#define OK 1
#define FALSE 0
#define ERROR -1
/************************************************************************/
/* 线性表的单链表存储结构*/
/************************************************************************/
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
/************************************************************************/
/* 操作结果：构造一个空的线性表L */
/************************************************************************/
void InitList(LinkList *L)
{
*L = (LinkList)malloc(sizeof(struct LNode)); /* 产生头结点，并使L指向此头结点 */
if( !*L ) /* 存储分配失败 */
exit(OVERFLOW);
(*L)->next = NULL; /* 指针域为空 */
}
/************************************************************************/
/* 在带头结点的单链线性表L中第i个位置之前插入元素e */
/************************************************************************/
Status ListInsert(LinkList L, int i, ElemType e)
{
int j = 0;
LinkList p = L, s;
while( p && j < i-1) /* 寻找第i-1个结点 */
{
p = p->next;
j++;
}
if( !p|| j > i-1) return ERROR;/* i小于1或者大于表长 */
s = (LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
s->data = e; /* 插入L中 */
s->next = p->next;
p->next = s;
return OK;
}
/************************************************************************/
/* 初始条件：线性表L已存在。操作结果：依次对L的每个数据元素调用函数vi() */
/************************************************************************/
void ListTraverse(LinkList L, void(*vi)(ElemType))
{
LinkList p = L->next;
while(p)
{
vi(p->data);
p = p->next;
}
printf("\n");
}
void printInt(int data)
{
printf("%d ", data);
}
void ListSort3(LinkList L)
{
LinkList first; //指向链表L第一个结点，除头结点
LinkList pre; //指向first的前驱结点
LinkList last; //指向first指向排好序的最后一个结点
LinkList rest; //指向未排好序的第一个结点，即链表第二个结点
LinkList curr; //指向当前结点
first = L->next; //指向第一个结点
if(first == NULL) return;
pre = L ; //pre指向first的前驱结点
last = first; //last指向排好序的最后一个结点
rest = first->next; //指向剩余的结点
first->next = NULL; //first断链
while (rest) //当余下的结点不为空
{
//保存当前结点
curr = rest;
//取下一个结点
rest = rest->next;
//当结点小于第一个结点，则链接到first前面
if( curr->data < first->data )
{
pre->next = curr;
curr->next = first;
pre = curr;
}
//当前结点大于第一个结点，则链接到last后
else if(curr->data > first->data)
{
curr->next = last->next;
last->next = curr;
last = curr;
}
//当前结点与第一个结点相等，则链接到first后面
else
{
curr->next = first->next;
first->next = curr;
}
}
}
void main()
{
LinkList L;
InitList(&L);
ListInsert(L, 1, 6);
ListInsert(L, 2, 3);
ListInsert(L, 3, 67);
ListInsert(L, 4, 2);
ListInsert(L, 5, 15);
ListInsert(L, 6, 13);
ListInsert(L, 7, 10);
ListInsert(L, 8, 6);
ListInsert(L, 9, 4);
ListSort3(L);
ListTraverse(L, printInt);
}
程序代码：