纯C手撕leetcode-基本数据结构-链表-148.排序链表

https://leetcode-cn.com/problems/sort-list/
思路：

1. 新链表头；
2. 插入排序；
3. 将已经排序的部分直接插入；

struct ListNode* sortList(struct ListNode* head){
    if (head == NULL || head->next == NULL)
        return head;

    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->val = INT_MIN;
    dummy->next = NULL;

    //1. 将已经排序的部分直接插入;
    struct ListNode* tail = head;
    struct ListNode* tailnext = tail->next;
    while(tailnext) {
        if (tailnext->val < tail->val)
            break;
        tail = tail->next;
        tailnext = tail->next;
    }

    tail->next = NULL;
    dummy->next = head;

    //2. 接着处理剩下的node
    struct ListNode* cur = tailnext;
    while(cur) {
        struct ListNode* next = cur->next;
        //--------找到合适位置，并插入开始-------
        //(1) 找到合适的位置
        struct ListNode* p = dummy;
        struct ListNode* pNext = dummy->next;
        while(pNext) {
            if ((cur->val <= pNext->val))
                break;
            
            p = pNext;
            pNext = p->next;
        }
        //(2)插入对应的位置
        cur->next = pNext;
        p->next = cur;
        //--------找到合适位置，并插入结束-------
        cur = next; //处理下一个node
    }

    struct ListNode* retH = dummy->next;
    free(dummy);
    return retH;
}