在C中对链表进行插入排序

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* insertionSortList(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode* curr = head->next;
    struct ListNode* prev = head;
    
    while (curr != NULL) {
        if (curr->val < prev->val) {
            struct ListNode* temp = dummy;
            while (temp->next->val < curr->val) {
                temp = temp->next;
            }
            prev->next = curr->next;
            curr->next = temp->next;
            temp->next = curr;
            curr = prev->next;
        } else {
            curr = curr->next;
            prev = prev->next;
        }
    }
    
    struct ListNode* newHead = dummy->next;
    free(dummy);
    return newHead;
}

struct ListNode* head = ...; // 链表的头节点
struct ListNode* sortedHead = insertionSortList(head);