c版基于链表的插入排序（改进版）

1. [代码][C/C++]代码     

/**
 * @todo    c版基于链表的插入排序
 * @author  Koma
 **/
#include
#include
 
typedef struct node{
    int data;
    struct node *next;
}LNode, *LinkList;
 
/**
 * 创建并初始化一个带头节点的链表
 **/
LinkList init() {
    LinkList p, r, list;
    list = (LinkList)malloc(sizeof(LNode));
    list->next = NULL;
    int e;
    while ( scanf("%d", &e) != 0 ) {
        p = (LinkList)malloc(sizeof(LNode));
        p->data = e;
        p->next = NULL;
        if ( !list->next ) {
            list->next = p;
        } else {
            r->next = p;
        }
        r = p;
    }
    return list;
}
 
 
/**
 * 打印链表 
 **/
void printLink( LinkList l ) {
    LinkList q;
    q = l->next;
    while ( q->next != NULL ) {
        printf("%d ", q->data);
        q = q->next;
    }
    printf("%d\n", q->data);
}
 
void innserSort( LinkList list1, LinkList q ) { 
    int in;     //标志量
    LinkList p, t, r;
     
    in = 0;
    r = p = list1;
    t = (LinkList)malloc(sizeof(LNode));
    t->next = NULL;
    t->data = q->data;
    if ( !p->next ) {
        p->next = t;
    } else {
        while ( p->next != NULL ) {
            r = p;
            p = p->next;
            if ( t->data > p->data ) {
                continue;
            } else {
                r->next = t;
                t->next = p;
                in = 1;
                break;
            }
        }
        //处理新链最后一个元素
        if ( !in ) {
            p->next = t;
        }
    }
}
 
/**
 * 实现插入排序
 **/
LinkList sort( LinkList l ) {
    LinkList q, list1;
     
    list1 = (LinkList)malloc(sizeof(LNode));
    list1->next = NULL;
    q = l->next;
    while ( q->next != NULL ) {
        innserSort(list1, q);
        q = q->next;
    }
    //处理旧链最后一个元素
    innserSort(list1, q);
    return list1;
}
 
int main() {
    LinkList l, l1;
    l = init();
    printLink(l);
    l1 = sort(l);
    printLink(l1);
    printLink(l);
    return 0;
}