1,定義一個已經(jīng)排序好的鏈表sort = NULL.
2,循環(huán)從當(dāng)前節(jié)點取出node插入到sort中
*需要主要的是，在插入sort前需要保持head->next,否則插入后保持值就不對

3，在插入函數(shù)邏輯中就是找到第一個大于等于需要插入節(jié)點的節(jié)點，然后放在這個節(jié)點前面，如果找不到，就插入到末尾

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;
}