C语言代码实现带头结点的单链表插入排序

下面是一个使用C语言实现带头结点的单链表插入排序的示例代码：

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

// 定义链表结点结构
typedef struct ListNode {
    int data;
    struct ListNode* next;
} ListNode;

// 创建新结点
ListNode* createNode(int data) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 插入结点到链表末尾
void insertNode(ListNode** head, int data) {
    ListNode* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
    } else {
        ListNode* curr = *head;
        while (curr->next != NULL) {
            curr = curr->next;
        }
        curr->next = newNode;
    }
}

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

// 单链表插入排序
void insertionSort(ListNode** head) {
    if (*head == NULL || (*head)->next == NULL) {
        return;
    }
    
    ListNode* sortedList = *head;
    ListNode* curr = sortedList->next;
    sortedList->next = NULL;
    
    while (curr != NULL) {
        ListNode* prev = NULL;
        ListNode* temp = curr;
        curr = curr->next;
        
        if (temp->data < sortedList->data) {
            temp->next = sortedList;
            sortedList = temp;
        } else {
            ListNode* search = sortedList;
            while (search != NULL && temp->data > search->data) {
                prev = search;
                search = search->next;
            }
            prev->next = temp;
            temp->next = search;
        }
    }
    
    *head = sortedList;
}

int main() {
    ListNode* head = NULL;
    insertNode(&head, 5);
    insertNode(&head, 3);
    insertNode(&head, 8);
    insertNode(&head, 1);
    insertNode(&head, 6);
    
    printf("排序前的链表：");
    printList(head);
    
    insertionSort(&head);
    
    printf("排序后的链表：");
    printList(head);
    
    return 0;
}

这段代码会创建一个带头结点的单链表，并使用插入排序算法对链表进行排序。在 `main` 函数中，我们插入了一些随机的整数，然后调用 `insertionSort` 函数进行排序，最后打印出排序后的链表。