#include <stdio.h>
#include <malloc.h>
//定义单链表结点
typedef struct node{    //这里用使用typedef定义新的数据类型
    int data;//数据域
    struct node *next;//指针域
}node;//定义别名,在其他地方才可以使用node这个命名

//创建链表（输入数据数组，返回头指针）
node* create(int a[])
{
    node *p, *L, *head;
    int i;
    head = (node *) malloc(sizeof(node));//分配内存
    head->next= NULL;
    L = head;
    for(i=0; i<5; i++)
    {
        p = (node *)malloc(sizeof(node));
        p->data = a[i];
        p->next = L->next;
        L->next = p;
    }
    return head;
}
//递增排序单链表（直接插入）
void sort(node* L)
{
    node *p = L->next, *pre;
    node *r = p->next;
    p->next = NULL;  //先将链表分成两条独立的链，头结点L指向的链只带有一个结点
    p = r;
    //将p指向的另一条链，比较大小后，在合适的位置插入到主链
    while(p!= NULL)
    {
        r = p->next;
        pre = L;
        //pre从头结点的next开始往下找，直到找到第一个大于p.data的结点 或者 pre.next为null
        while(pre->next!=NULL && pre->next->data < p->data)
         ...