147 insertion sort list

1,定义一个已经排序好的链表sort = NULL.
2,循环从当前节点取出node插入到sort中
*需要主要的是，在插入sort前需要保持head->next,否则插入后保持值就不对

3，在插入函数逻辑中就是找到第一个大于等于需要插入节点的节点，然后放在这个节点前面，如果找不到，就插入到末尾

struct ListNode *insert(struct ListNode *sorted, struct ListNode *node)
{
    struct ListNode *dummyhead = malloc(sizeof(struct ListNode));
    dummyhead->next = sorted;
    struct ListNode *prev, *curr;
    struct ListNode *ret;
    curr = sorted;
    prev= dummyhead;
    while(curr){
        if(node->val <= curr->val)
        {
            //insert before curr
            node->next = curr;
            prev->next = node;
            ret = dummyhead->next;
            free(dummyhead);
            return ret;

        }else{
            curr = curr->next;
            prev = prev->next;
        }
    }

    prev->next = node;
    node->next = NULL;
    ret = dummyhead->next;
    free(dummyhead);
    return ret;
}

struct ListNode* insertionSortList(struct ListNode* head) {

    struct ListNode * sorted = NULL;
    struct ListNode * node;
    while(head){
        node = head;
        head = head->next;
        sorted = insert(sorted, node);
        
    }
    
    return sorted;
}