设L为单链表（带头结点），其中每个结点由一个整数域data和指针域next组成,……设L为单链表（带头结点），其中每个结点由一个整数域data和指针域next组成，整数域data中的数据都是正整

Question

设L为单链表（带头结点），其中每个结点由一个整数域 data和指针域next组成,……
设L为单链表（带头结点），其中每个结点由一个整数域 data和指针域next组成，整数域 data中的数据都是正整数且无相同的，试设计原地将该链表整理成数据递增的有序单链表的算法。

Answer 1

呵呵，刚做完一个差不多的程序，分享下。
#include
#include
#include
typedef struct node
{
int data;
struct node *next;
}Node;
void InitList(Node **head);
void CreateList(Node **head);
void InsertList(Node **head, int key);
void DeleteList(Node **head, int key);
void PrintList(Node **head);
void paixu(Node **head);
//初始化链表
void InitList(Node **head)
{
(*head) = (Node *)malloc(sizeof(Node));
(*head)->next = NULL;
}
//创建链表
void CreateList(Node **head)
{
int i;

printf("请输入要插入的数据(以0结束):\n");
scanf("%d", &i);
while(i != 0)
{
InsertList(head, i);
scanf("%d", &i);
}
}
//插入链表
void InsertList(Node **head, int key)
{
Node *p, *q, *s;
q = (*head);
p = (*head)->next;
while(p)
{
q = p;
p = p->next;
}
s = (Node *)malloc(sizeof(Node));
s->data = key;
s->next = NULL;
q->next = s;
}
//删除链表
void DeleteList(Node **head, int key)
{
Node *p, *q;

q = (*head);
p = (*head)->next;
while(p && p->data != key)
{
q = p;
p = p->next;
}
if(p)
{
q->next = p->next;
free(p);
p = NULL;
}
}
//输出链表
void PrintList(Node **head)
{
Node *p;

p = (*head)->next;
while(p)
{
printf("%d\n", p->data);
p = p->next;
}
}
//排序链表
void paixu(Node **head)
{
Node *p,*q,*t,*s;
p=(*head)->next;
if(p==NULL) return;//没有节点
s=p->next;
if(s==NULL) return;//只有一个节点

p->next=NULL;//把链表截断成只有1个节点

while(s!=NULL)
{
t=s->next;//先记住下一个要处理的节点
s->next=NULL;//把当前节点独立出来

//从当前有序链表中查找插入点
q=(*head);
p=(*head)->next;
while(p!=NULL&&p->datadata)
{
q=p;
p=p->next;
}
//循环出来后，q是新插入节点的前驱，p是后继
q->next=s;
s->next=p;

//把之前记录的待处理节点传给s,以便循环继续处理未处理的节点
s=t;
}
}
int main(void)
{
Node *head;
int i;
InitList(&head);

CreateList(&head);
printf("删除前的数据:\n");
PrintList(&head);
printf("请输入要删除的数据:\n");
fflush(stdin);
scanf("%d", &i);
DeleteList(&head, i);
printf("删除后的数据:\n");
PrintList(&head);

paixu(&head);
printf("排序后的数据:\n");
PrintList(&head);

return 0;
}