38-9

给定一个带头结点的单链表，按递增次序输出单链表中各结点的数据元素，并释放空间。不允许使用辅助数组

使用直接插入排序，将链表递增，然后进行遍历删除操作

时间复杂度为O(N²)

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
    int data;
    struct node *next;
}LNode,*LinkList;

void TailCreate(LinkList &L)
{
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    LNode *p,*r=L;
    int x;
    scanf("%d",&x);
    while(x!=999)
    {
        p=(LNode*)malloc(sizeof(LNode));
        p->data=x;
        p->next=NULL;
        r->next=p;
        r=p;
        scanf("%d",&x);
    }
}

void displayList(LinkList L)
{
    LNode *p=L->next;
    while(p!=NULL)
    {
        printf("%d  ",p->data);
        p=p->next;
    }
}

void Delete(LinkList &L)
{
    LNode *pre,*r,*p=L->next;
    r=p->next;
    L->next=NULL;
    while(p)
    {
        r=p->next;
        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
        p->next=pre->next;
        pre->next=p;
        p=r;
    } 
    p=L->next;
    while(p)
    {
        printf("%d ",p->data);
        r=p;
        p=p->next;
        free(r);
    }
    free(L);
} 

int main()
{
    LinkList L;
    TailCreate(L);
    displayList(L);
    printf("\n");
    Delete(L);
    return 0;
}