147. Insertion Sort List - cocoder39/coco39_LC GitHub Wiki

147. Insertion Sort List

if (head->next->val >= head->val) {
                head = head->next;
            } 

is an optimization

ListNode* insertionSortList(ListNode* head) {
        if (! head) { 
            return head;
        }
        
        ListNode dummy(0);
        dummy.next = head;
        
        while (head->next) {
            if (head->next->val >= head->val) {
                head = head->next;
            } 
            else {
                ListNode* cur = head->next;
                head->next = cur->next;
                ListNode* start = &dummy;
                while(cur->val > start->next->val){
                    start = start->next;
                }
                cur->next = start->next;
                start->next = cur;
            }
        }
        return dummy.next;
    }