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

Question

（c语言）（线性表）已知一双向循还链表，从第二个结点至表尾递增有序，（设a1<x<an）.试编写程序，将第一个结点删除并插入表中适当位置，使整个链表递增有序。
输入
输入长度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

Answer 1

该回答引用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;
}