用c语言实现 用直接插入排序法对链表C进行升序排序，生成链表D，并输出D

假设链表节点的结构体定义如下：

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

则可以按照以下步骤实现直接插入排序法：

1. 新建一个头节点 `dummy`，并将其 `next` 指向链表 `C` 的头节点。

2. 遍历链表 `C`，对于每个节点，将其从链表 `C` 中删除，并插入到链表 `D` 中的正确位置。

3. 遍历完成后，将 `dummy->next` 指向链表 `D` 的头节点。

具体实现如下：

ListNode* insertionSortList(ListNode* head) {
    ListNode dummy = {0, head};
    ListNode *p = head, *prev = &dummy;
    while (p) {
        ListNode *q = &dummy;
        while (q != prev && q->next->val <= p->val) {
            q = q->next;
        }
        if (q == prev) {
            prev = prev->next;
            p = p->next;
        } else {
            prev->next = p->next;
            p->next = q->next;
            q->next = p;
            p = prev->next;
        }
    }
    return dummy.next;
}

调用方式如下：

ListNode* C; // 原始链表
ListNode* D = insertionSortList(C); // 排序后的链表
// 输出链表D
while (D) {
    printf("%d ", D->val);
    D = D->next;
}