/* link.h
#define NULL 0
#include<malloc.h>
#include <stdio.h>
typedef int datatype;
typedef struct link_node{
datatype info;
struct link_node *next;
}node;
typedef node* nodelink;

nodelink buildlink() /* 尾插法*/
{

datatype x;
nodelink head,s;
nodelink p2;
head=NULL;
p2=NULL;
printf("please input the link:");
scanf("%d",&x);
while(x!=0)
{s=(nodelink)malloc(sizeof(node));
s->info=x;
if (head==NULL) head=s; else p2->next=s;
p2=s;
scanf("%d",&x);
}
if(p2) p2->next=NULL;
return(head);
}

nodelink creatlink() /***头插法***/
{ nodelink head,p;
datatype x;
head=NULL;
printf("please input the link:");
scanf("%d",&x);
while(x!=0)
{ p=(nodelink)malloc(sizeof(node)) ;
p->info=x;
p->next=head;
head=p;
scanf("%d",&x);
}
return head;
}

void print_link_list(nodelink head)
{ nodelink p;
p=head;
while(p)
{ printf("%5d-->",p->info);
p=p->next;
}
printf("\n");
}
*/


#include"link.h"
/*单链表头文件*/
/*从链表中拆出节点，插入到一新链表中*/

nodelink paixu(nodelink*head1)
{
nodelink p,pre,s,q,head ;
p=*head1;
pre=NULL;
head=NULL;
s=head;
q=NULL;
while(p!=NULL)
{
pre=p->next ;
/*保留P的原值，以便下一次访问*/
p->next=NULL ;
if(head==NULL)head=p ;
else
{
s=head ;
q=NULL ;
/*没找到，下移*/
while((s!=NULL)&&(p->info<=s->info))
{
q=s ;
s=s->next ;
}
if(q==NULL)
{
p->next=head ;
head=p ;
}
else
{
p->next=s ;
q->next=p ;
}
}
p=pre ;
}
return(head);
}

main()
{
nodelink head1,head ;
head1=buildlink();
printf("input the start link:");
print_link_list(head1);
/*打印链表*/
head=paixu(&head1);
/*核心函数，将单链表排序*/
printf("input the end link:");
print_link_list(head);
/*打印链表*/
getch();
}