c语言 实现双向链表动态插入排序

额。。。不太容易实现，因为链表这种数据结构会遇到很多边界问题，需要比较复杂的判断边界的操作。
要是笔试遇到这种题，自求多福？？？

其实可以偷懒一点点，先放数据到数组里面，在数组里面选择排序，然后把有序数组循环尾插到链表中。但是这样的话每次插入新数据都要销毁整个链表并且重新创建一个链表，时间复杂度较高。

下面是真正动态插入的方法，在qt creator上测试通过

#include <stdio.h>
#include<malloc.h>
/************tonytrek 2021.7.15**************/
typedef struct n{
    int data;
    struct n* next;
    struct n* front;
}node,*pnode;

pnode create_node();
int sort_add_node(pnode,int);
int add_to_tail_of_certain_node(pnode,int);
int show_list(pnode);

int main()
{
    int arry[6]={1,9,2,8,5,3};
    pnode head=create_node();
    for(int i=0;i<6;i++)
    {
        sort_add_node(head,arry[i]);
    }
    show_list(head);
    sort_add_node(head,0);
    show_list(head);
    return 0;
}

pnode create_node()
{
     pnode new_node=(pnode)malloc(sizeof(node));
     new_node->data=0;
     new_node->next=NULL;
     new_node->front=NULL;
     return new_node;
}

int sort_add_node(pnode head,int num)
{
    pnode p;
    p=head;
    if(p->next!=NULL&&num<p->next->data)
    {
        add_to_tail_of_certain_node(head,num);
    }
    else if(p->next==NULL)
    {
        add_to_tail_of_certain_node(p,num);
    }
    else{
    while(num>p->data)
    {
        if(p->next!=NULL&&num>p->next->data)
        {
            p=p->next;
            continue;
        }
        else
        {
            add_to_tail_of_certain_node(p,num);
            break;
        }
    }
    }
    return 0;
}

int add_to_tail_of_certain_node(pnode anode,int num)
{
    pnode tmp=anode;
    pnode new_node=(pnode)malloc(sizeof(node));
    new_node->data=num;
    new_node->front=anode;
    new_node->next=anode->next;
    anode->next=new_node;
    if(tmp->next!=NULL)
        tmp->next->front=new_node;
    return 0;
}

int show_list(pnode head)
{
    pnode p=head->next;
    while(p->next!=NULL)
    {
        printf("%d",p->data);
        p=p->next;
    }
    printf("%d\n",p->data);
    return 0;
}