链表排序算法c语言

链表排序可以使用多种算法实现，下面是一种基于插入排序的链表排序算法的C语言实现：

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

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

/* 插入排序算法实现 */
ListNode* insertionSortList(ListNode* head) {
    if (!head || !head->next) return head;  // 链表为空或只有一个节点，直接返回
    ListNode *dummy = (ListNode *)malloc(sizeof(ListNode));  // 创建哑节点
    dummy->next = head;
    ListNode *p = head->next, *q = head;  // p指向要插入的节点，q指向p的前一个节点
    while (p) {
        ListNode *r = dummy;  // r指向已排序部分的哑节点
        while (r != q && r->next->val <= p->val) r = r->next;  // 在已排序部分中找到插入位置
        if (r != q) {
            q->next = p->next;
            p->next = r->next;
            r->next = p;
            p = q->next;
        } else {
            p = p->next;
            q = q->next;
        }
    }
    head = dummy->next;
    free(dummy);  // 释放哑节点
    return head;
}

/* 创建链表 */
ListNode* createList(int arr[], int n) {
    if (n == 0) return NULL;
    ListNode *head = (ListNode *)malloc(sizeof(ListNode));
    head->val = arr[0];
    head->next = NULL;
    ListNode *p = head;
    for (int i = 1; i < n; i++) {
        ListNode *q = (ListNode *)malloc(sizeof(ListNode));
        q->val = arr[i];
        q->next = NULL;
        p->next = q;
        p = p->next;
    }
    return head;
}

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

int main() {
    int arr[] = {3, 1, 4, 2, 5};
    int n = sizeof(arr) / sizeof(int);
    ListNode *head = createList(arr, n);
    printf("原链表：");
    printList(head);
    head = insertionSortList(head);
    printf("排序后：");
    printList(head);
    return 0;
}

该程序中，insertionSortList函数实现了链表的插入排序算法，createList函数用来创建链表，printList函数用来打印链表。在main函数中，先创建一个链表，然后打印原链表，对链表进行排序，最后再打印排序后的链表。