排序(线性表)

时间： 1ms 内存：128M

描述：

（线性表）已知不带头结点的线性链表node，链表中结点构造为（data、next），其中data为数据域，next为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。

#include <stdio.h>
#include <stdlib.h> //对应malloc函数
struct Node
{
    int data;
    struct Node *next;
};
struct Node *creat(struct Node *head)   //尾插建表
{
    int n,i;
    struct Node *current=NULL,*previous=NULL;
    head=NULL;
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
        current=(struct Node*)malloc(sizeof(struct Node));
        scanf("%d",&current->data);
        current->next=NULL;
        if(i==1)
            head=current;    //链表头
        else
            previous->next=current;
        previous=current;
    }
    return head;
}
struct Node *sort(struct Node *head)    //插入排序
{
    struct Node *unsorted,*previous,*current,*sorted,*inserted;
    if(head==NULL)
        return NULL;
    unsorted=head->next; //剩余未排序链表
    head->next=NULL;    //摘下首结点
    sorted=head;        //已排序链表
    while(unsorted!=NULL) //还有未排序结点
    {
        inserted=unsorted;   //当前插入结点
        unsorted=unsorted->next;

        current=sorted;
        while((current!=NULL)&&(current->data<inserted->data))
        {
            previous=current;
            current=current->next;
        }
        if(current==sorted)    //插入到链表的头部
            sorted=inserted;
        else
           /**************/

          添加代码

           /**************/

    }
    return sorted;
}
void destroy(struct Node *head)
{
struct Node *p;
while(head!=NULL)
{
  p=head->next;
  delete(head);
  head=p;
}
}
int main()
{
    struct Node *head=NULL;
    head=creat(head);
    head=sort(head);
    while(head!=NULL)
    {
        printf("%d ",head->data);
        head=head->next;
    }
    destroy(head);
    return 0;
}