一个结点删除并插入表中适当位置，使整个链表递增有序

（c语言）（线性表）已知一双向循还链表，从第二个结点至表尾递增有序，（设a1输入
输入长度n：7
输入数据：4 1 2 3 6 8 9
输出
1 2 3 4 6 8 9
样例输入
5
11 7 8 9 10
样例输出
7 8 9 10 11

该回答引用ChatGPT

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int data;
    struct Node *prev;
    struct Node *next;
} Node;
// 创建双向循环链表
Node *createList(int n) {
    Node *head, *tail, *p;
    head = (Node *) malloc(sizeof(Node));
    tail = head;
    for (int i = 0; i < n; i++) {
        p = (Node *) malloc(sizeof(Node));
        scanf("%d", &p->data);
        tail->next = p;
        p->prev = tail;
        tail = p;
    }
    tail->next = head->next;
    head->next->prev = tail;
    free(head);
    return tail->next;
}
// 打印链表
void printList(Node *head) {
    Node *p = head;
    do {
        printf("%d ", p->data);
        p = p->next;
    } while (p != head);
    printf("\n");
}
// 在有序链表中找到第一个大于等于x的结点
Node *findNode(Node *head, int x) {
    Node *p = head;
    while (p->next != head->next && p->next->data < x) {
        p = p->next;
    }
    return p;
}
// 在链表中插入结点
void insertNode(Node *p, Node *q) {
    q->prev = p->prev;
    p->prev->next = q;
    q->next = p;
    p->prev = q;
}
// 删除链表中的结点
void deleteNode(Node *p) {
    p->prev->next = p->next;
    p->next->prev = p->prev;
    free(p);
}
// 将第一个结点删除并插入表中适当位置，使整个链表递增有序
Node *sortList(Node *head) {
    Node *p = head->next;
    head->next = p->next;
    p->next->prev = head;
    Node *q = findNode(head, p->data);
    insertNode(q, p);
    return head;
}
int main() {
    int n;
    scanf("%d", &n);
    Node *head = createList(n);
    head = sortList(head);
    printList(head);
    return 0;
}

供参考：

//双向循环链表

#include <stdio.h>
#include <stdlib.h>
typedef struct linklist
{
    int      data;
    linklist* next, * pre;
} Dulinklist;
void InitDuList(Dulinklist** head)
{
    (*head) = (Dulinklist*)malloc(sizeof(Dulinklist));;
    (*head)->next = (*head)->pre = (*head);
}
void CreatDuList(Dulinklist* head, int n)
{
    Dulinklist* p = NULL, * q = head;
    while (n--)
    {
        p = (Dulinklist*)malloc(sizeof(Dulinklist));
        scanf("%d", &p->data);
        q->next = p;
        p->pre = q;
        p->next = head;
        head->pre = p;
        q = p;
    }
}
void split(Dulinklist* head)
{
    Dulinklist* pt = NULL, * ph = NULL;
    if (head->next == head)  return; //链表只有一个结点，则不做拆分操作

    pt = head->next; //提取出链表的第一个结点 pt
    pt->next->pre = pt->pre;
    pt->pre->next = pt->next;
    pt->pre = NULL;
    pt->next = NULL;

    ph = head->next; //将第一个结点 pt 插入表中适当位置
    while (ph != head && ph->data < pt->data) ph = ph->next;
    ph->pre->next = pt;
    pt->next = ph;
    pt->pre = ph->pre;
    ph->pre = pt;
}
void printlist_F(Dulinklist* head)//正向输出
{
    Dulinklist* p = head->next;
    while (p != head)
    {
        printf("%d ", p->data);
        p = p->next;
    }
}
void printlist_R(Dulinklist* head) //反向输出
{
    Dulinklist* p = head->pre;
    while (p != head)
    {
        printf("%d ", p->data);
        p = p->pre;
    }
}
int main()
{
    Dulinklist* head = NULL;
    int n;
    printf("输入长度n:");
    scanf("%d", &n);
    InitDuList(&head);
    CreatDuList(head, n);
    split(head);
    printlist_F(head);
    //printlist_R(head);
    return 0;
}

自己写个数据结构也好啊

用数据结构实现list，再用一个变量存储第一个结点。
对list进行 头删pop_front() 操作。
循环遍历list，如果遇到大于当前结点，且小于当前节点的后继节点，则在当前节点后插入，退出循环。
在次遍历列表进行输出。

优化
在查找插入位置时，每遍历一个元素就输出，找到之后不退出，继续输出。