147. Insertion Sort List

147. Insertion Sort List:题目链接

方法1

struct ListNode* insertionSortList(struct ListNode* head){
    struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    dummyHead->next = head;
    if (head == NULL) {
       return head;
    }  
    struct ListNode* pre = NULL;   // pre:待排元素在链表中的正确排序下的前驱
    struct ListNode* cur = head;   
    struct ListNode* next = NULL;  // next:待排序节点
    while (cur->next != NULL) {
        next = cur->next;
        if (cur->val <= next->val) { // 待排序节点 >= 前面节点 说明有序 遍历下一个
            cur = cur->next;
        }else{
            pre = dummyHead; 
            while (pre->next != NULL && pre->next->val <= next->val) { // 从链表头开始 找到待排节点要插入位置的前驱
                pre = pre -> next;
            }
            // 找到前驱 开始插入
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
        }
    }
    return dummyHead->next;
}

/*
Runtime: 4 ms, faster than 100.00% of C online submissions for Insertion Sort List.
*/