给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3. 重复直到所有输入数据插入完为止。

下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

对链表进行插入排序。

思路一：模拟题意

c语言解法

struct ListNode *insertionSortList(struct ListNode *head) {
    if (head == NULL) {
        return head;
    }
    struct ListNode *dummyHead = malloc(sizeof(struct ListNode));
    dummyHead->val = 0;
    dummyHead->next = head;
    struct ListNode *lastSorted = head;
    struct ListNode *curr = head->next;
    while (curr != NULL) {
        if (lastSorted->val <= curr->val) {
            lastSorted = lastSorted->next;
        } else {
            struct ListNode *prev = dummyHead;
            while (prev->next->val <= curr->val) {
                prev = prev->next;
            }
            lastSorted->next = curr->next;
            curr->next = prev->next;
            prev->next = curr;
        }
        curr = lastSorted->next;
    }
    return dummyHead->next;
}

c++解法

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* headnode = new ListNode(INT_MIN);
        ListNode* tail = headnode;
        ListNode* p = head;
        while (p) {
            auto tmp = p->next;
            ListNode* q = headnode;
            while (q->next && q->next->val < p->val) {
                q = q->next;
            }
            p->next = q->next;
            q->next = p;
            p = tmp;
        }
        return headnode->next;
    }
};

分析：

本题将链表通过插入排序，不断输入新节点将节点放到链表的正确位置，当最后的节点递归到应放的位置后插入，最后输出排序好的链表

总结：

本题考察对链表排序的操作，利用判断是否节点值大于现链表尾部值判断节点应放到哪个地方，最后返回链表即可解决