无头单链表排序

（1）无头头插单链表排序：

（思路：在原链表中逐个比较大小，将最小的插入新的链表（插入顺序按照尾插的顺序））

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

typedef struct person
{
    int age;
    struct person *next;
}per;

per *head_list(per *one, int num)   //头插
{
    per *temp = (per *)malloc(sizeof(per));

    temp->age = num;
    temp->next = one;

    return temp;
}

void show(per *head)    //遍历
{
    if(NULL == head)
    {
        return;
    }
    while(head)
    {
        printf("age is %d\n",head->age);
        head = head->next;
    }
}

void *sort(per *head)   //排序
{
    if(NULL == head)    //若链表为空则不用排序
    {
        return NULL;
    }
    if(NULL == head->next)  //若链表中只有一个数，则不用比较
    {
        printf("min is head\n");
        return;
    }
    per *min_pre = NULL;
    per *min = head;
    per *tmp = head;
    per *new_list = NULL;   
    per *tail_sort = NULL;

    while(head)
    {
        min = head;
        tmp = head;
        while(tmp->next)
        {
            if(min->age > tmp->next->age)
            {
                min = tmp->next;
                min_pre = tmp;
            }
            tmp = tmp->next;
        }
        if(min == head)
        {
            head = head->next;
        }
        else
        {
            min_pre->next = min->next;
            min->next = NULL;
        }
        if(NULL == new_list)    //按照尾插将最小的数组成新的链表
        {
            tail_sort = min;
            new_list = tail_sort;
        }
        else
        {
            tail_sort->next = min;
            tail_sort = min;
        }
    }
    return new_list;
}

int main()
{
    int i = 6;
    per *head = NULL;

    while(i--)
    {
        head = head_list(head,rand() % 100);    //rand()伪随机函数，取100以内的随机数
    }

    show(head);
    printf("=======after sort========\n");

    head = sort(head);
    show(head);

    return 0;
}
           

（2）无头尾插单链表排序：

（思路：在原链表中逐个比较大小，将最小的插入新的链表（插入顺序按照头插的顺序））

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

typedef struct person
{
    int age;
    struct person *next;
}per;

per *tail_list(per *one, int num)   //尾插
{
    per *temp = (per *)malloc(sizeof(per));

    temp->age = num;
    if(NULL == one)
    {
        return temp;
    }
    per *head = one;

    while(one->next)
    {
        one = one->next;
    }
    one->next = temp;

    return head;
}

void show(per *head)
{
    if(NULL == head)
    {
        return;
    }
    while(head)
    {
        printf("age is %d\n",head->age);
        head = head->next;
    }
}

per *sort(per *head)
{
    if(NULL == head)
    {
        return;
    }
    if(NULL == head->next)
    {
        printf("min is head\n");
        return;
    }
    per *min = head;
    per *tmp = head;
    per *min_pre = NULL;
    per *new_list = NULL;
    per *tail_list = NULL;

    while(head)
    {
        min = head;
        tmp = head;
        while(tmp->next)
        {
            if(min->age > tmp->next->age)
            {
                min = tmp->next;
                min_pre = tmp;
            }
            tmp = tmp->next;
        }
        if(min == head)
        {
            head = head->next;
            min->next = NULL;
        }
        else
        {
            min_pre->next = min->next;
            min->next = NULL;
        }
        min->next = new_list;   //头插顺序插入新链表
        new_list = min;
    }
    return new_list;
}


int main()
{
    int i = 6;
    per *head = NULL;
    while(i--)
    {
        head = tail_list(head,rand() % 100);
    }

    show(head);
    printf("=========after sort============\n");
    head = sort(head);
    show(head);

    return 0;
}