C语言链表排序怎么实现

实现C语言链表排序的一种常用方法是使用插入排序（Insertion Sort）算法。下面是实现链表排序的示例代码：

#include <stdio.h>#include <stdlib.h>// 定义链表节点结构体typedef struct ListNode {    int val;    struct ListNode* next;} ListNode;// 创建一个新的链表节点ListNode* createNode(int val) {    ListNode* node = (ListNode*)malloc(sizeof(ListNode));    node->val = val;    node->next = NULL;    return node;}// 插入排序算法ListNode* insertionSortList(ListNode* head) {    if (head == NULL || head->next == NULL) {        return head;    }        ListNode* sorted = head;  // 排序部分的链表    ListNode* cur = head->next;  // 待排序的部分链表        while (cur != NULL) {        if (cur->val < sorted->val) {  // 如果当前节点的值小于排序链表的头节点值            ListNode* tmp = cur->next;            cur->next = sorted;            sorted = cur;            cur = tmp;        }        else {  // 如果当前节点的值大于等于排序链表的头节点值            ListNode* pos = sorted;            while (pos->next != NULL && pos->next->val < cur->val) {                pos = pos->next;            }            ListNode* tmp = cur->next;            cur->next = pos->next;            pos->next = cur;            cur = tmp;        }    }        return sorted;}// 打印链表void printList(ListNode* head) {    ListNode* cur = head;    while (cur != NULL) {        printf("%d ", cur->val);        cur = cur->next;    }    printf("\n");}int main() {    // 创建链表    ListNode* head = createNode(4);    head->next = createNode(2);    head->next->next = createNode(1);    head->next->next->next = createNode(3);        // 打印原链表    printf("原链表：");    printList(head);        // 对链表进行排序    head = insertionSortList(head);        // 打印排序后的链表    printf("排序后：");    printList(head);        return 0;}

运行以上代码，输出结果如下：

原链表：4 2 1 3 排序后：1 2 3 4 

以上示例代码实现了对链表进行插入排序，时间复杂度为O(n^2)，其中n为链表的长度。