在一个有序(非递减)链表中插入新结点，使得新链表仍然有序。

#include <stdio.h>
#include <stdlib.h>
//在一个有序(非递减)链表中插入新结点，使得新链表仍然有序

//结点
struct linkNode{
    int data;
    struct linkNode *next;
};

void output(struct linkNode *head);                         //打印链表数据域

struct linkNode *creat_link_list_rear(int *a, int n);       //尾插法

struct linkNode *insert_sort(struct linkNode *h, int x);    //寻找位置插入结点

int main() {

    int a[6];               //存放结点数据
    int x;                  //带插入数据
    struct linkNode *head;  //头指针(尾插法)

    printf("输入数组各元素的值【6个】:\n");
    for(int i=0; i<6; i++){
        scanf("%d", &a[i]);
    }

    head = creat_link_list_rear(a, 6);     //尾插法

    printf("此链表各个节点的数据为：\n");
    output(head);

    printf("输入要插入的数据：\n");
    scanf("%d", &x);

    head = insert_sort(head, x);

    printf("\n插入新数据后，此链表各个节点的数据为：\n");
    output(head);

    return 0;
}


//尾插法
struct linkNode *creat_link_list_rear(int a[], int n){

    struct linkNode *h = NULL;  //新建链表h，将每个结点依次插入到链尾，将链表的头指针返回
    struct linkNode *s;         //要插入的结点
    struct linkNode *r;         //尾结点

    for(int i=0; i<n; i++){
        s = (struct linkNode *)malloc(sizeof(struct linkNode));
        s->data = a[i];
        s->next = NULL;

        if(h == NULL){
            h = s;
        }else{
            r->next = s;
        }

        r = s;  //r指向当前链表的尾结点
    }

    return h;   //返回链表头指针
}


//寻找位置插入结点
struct linkNode *insert_sort(struct linkNode *h, int x){
    struct linkNode *s;     //待插入结点
    struct linkNode *p;     //游标
    struct linkNode *pre;   //前驱

    s = (struct linkNode *)malloc(sizeof(struct linkNode));
    s->data = x;
    s->next = NULL;

    if (h == NULL){         //情况1. h为空链表
        h = s;
    }

    if (x <= h->data){      //情况2. x不大于链表中的第一个节点的数据域，将s插在链首
        s->next = h;
        h = s;
    }else{                  //情况3. 游标p指向头结点
        p = h;

        while (p && x > p->data){
            pre = p;
            p = p->next;
        }

        s->next = pre->next;
        pre->next = s;
    }

    return h;   //返回链表头结点
}


//打印链表数据
void output(struct linkNode *head){
    struct linkNode *p = head;

    while (p){
        printf("%d ", p->data);
        p = p->next;
    }

    printf("\n");
}