c语言链表排序插入排序

链表的插入排序可以考虑从头节点开始，依次将后面的节点插入到已排序好的链表中。

具体实现步骤如下：

1. 定义一个新的链表头节点`dummy`，并将其指向原链表的头节点。
2. 定义一个指针变量`cur`，用于遍历链表。
3. 定义一个指针变量`pre`，用于记录已排序好的链表的最后一个节点。
4. 从原链表的第二个节点开始遍历，依次将节点插入到已排序好的链表中。
5. 在已排序好的链表中找到插入位置，插入节点。
6. 遍历完整个链表后，返回`dummy->next`，即为排好序的链表。

以下是代码示例：

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

typedef struct Node {
    int val;
    struct Node *next;
} Node;

Node* insertSortList(Node* head) {
    Node *dummy = (Node*)malloc(sizeof(Node));
    dummy->next = head;

    Node *cur = head;
    Node *pre = dummy;

    while (cur) {
        if (cur->next && cur->next->val < cur->val) {
            // 找到要插入的位置
            while (pre->next && pre->next->val < cur->next->val) {
                pre = pre->next;
            }

            // 插入节点
            Node *temp = cur->next;
            cur->next = temp->next;
            temp->next = pre->next;
            pre->next = temp;
            pre = dummy;
        } else {
            cur = cur->next;
        }
    }

    return dummy->next;
}

int main() {
    Node *head = (Node*)malloc(sizeof(Node));
    head->val = 3;
    head->next = (Node*)malloc(sizeof(Node));
    head->next->val = 2;
    head->next->next = (Node*)malloc(sizeof(Node));
    head->next->next->val = 4;
    head->next->next->next = (Node*)malloc(sizeof(Node));
    head->next->next->next->val = 1;
    head->next->next->next->next = NULL;

    Node *res = insertSortList(head);

    while (res) {
        printf("%d ", res->val);
        res = res->next;
    }

    return 0;
}

输出结果为：1 2 3 4