c 语言链表插入排序完整代码

以下是C语言链表插入排序的完整代码实现：

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

// 链表节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 插入节点到链表头
Node* insertAtHead(Node* head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = head;
    return newNode;
}

// 创建链表
Node* createList(int arr[], int n) {
    Node* head = NULL;
    for (int i = n - 1; i >= 0; i--) {
        head = insertAtHead(head, arr[i]);
    }
    return head;
}

// 打印链表
void printList(Node* head) {
    Node* p = head;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

// 链表插入排序
Node* insertionSort(Node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    Node* p = head->next;
    Node* newHead = head;
    newHead->next = NULL;
    while (p) {
        Node* q = p->next;
        if (p->data < newHead->data) {
            p->next = newHead;
            newHead = p;
        } else {
            Node* prev = newHead;
            Node* cur = newHead->next;
            while (cur && p->data > cur->data) {
                prev = cur;
                cur = cur->next;
            }
            prev->next = p;
            p->next = cur;
        }
        p = q;
    }
    return newHead;
}

int main() {
    int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    Node* head = createList(arr, n);
    printf("排序前：");
    printList(head);
    head = insertionSort(head);
    printf("排序后：");
    printList(head);
    return 0;
}

以上代码中，先定义了链表节点结构体 `Node`，包含一个整型数据 `data` 和一个指向下一个节点的指针 `next`。然后定义了插入节点到链表头的函数 `insertAtHead` 和创建链表的函数 `createList`，并用其中的 `insertAtHead` 函数来创建链表。接下来定义了打印链表的函数 `printList`。

最后，定义了链表插入排序的函数 `insertionSort`，该函数的参数是链表头节点指针，返回排好序后的新链表头节点指针。在 `main` 函数中，创建链表并打印未排序的链表，然后调用 `insertionSort` 函数进行排序，并打印排好序后的链表。