【链表】对链表进行插入排序

解题思路：

从第二元素开始与子序列对比，同时用一个值length记录已经排好的值

因为是一个单链表，所以我们可以从链表的头元素开始，比较当前元素是否比要插入的元素小。

如果遍历到的元素大于等于要排序的元素，记录这个位置得值，然后将要排序的值插入，

struct ListNode* insertionSortList(struct ListNode* head){
    if(!head->next)
        return head;
    struct ListNode* curNode = head->next;
    struct ListNode* node = head;
    int length = 1;
    while(curNode) {
        int i;
        node = head;
        for(i = 0; i < length; i++) {
            if(node->val > curNode->val) {
                int temp = node->val;
                node->val = curNode->val;
                curNode->val = temp;
            }
            node = node->next;
        }
        curNode = curNode->next;
        length++;
    }

    return head;
}

解题思路：

若head为NULL或者链表中只有head，直接返回head

1.创建一个新的结点header，将header->next指向head，这样方便在head之前加入结点

2.创建两个指针curNode和lastSortedNode，将curNode指向head->next,lastSortedNode初始化指向head。然后比较他们的值：

a.若lastSortedNode的值小于curNode，证明不需要改变链表，将两个指针都后移一位即可

b.若lastSortedNode大于curNode，则代表需要插入curNode。我们设立一个新的指针pre，pre初始化指向header。通过pre->next->val找到该插入的位置，然后改变pre和curNode的指针来交换两个结点

3.返回header->next

struct ListNode* insertionSortList(struct ListNode* head){
    if(!head || !head->next)
        return head;
    struct ListNode* header = (struct ListNode*)malloc(sizeof(struct ListNode));
    header->val = 0;
    header->next = head;
    struct ListNode* curNode = head->next;
    struct ListNode* lastSortedNode = head;
    while(curNode) {
        if(lastSortedNode->val > curNode->val) {
            struct ListNode* pre = header;
            while(pre->next->val < curNode->val)
                pre = pre->next;
            lastSortedNode->next = curNode->next;
            curNode->next = pre->next;
            pre->next = curNode;
        } else {
            lastSortedNode = lastSortedNode->next;
        }
        curNode = lastSortedNode->next;
    }
    return header->next;
}