10 line clean and easy-to-understand C++ solution


  • 6
    X

    Please see my blog post for more.

    ListNode *insertionSortList(ListNode *head) {
        ListNode dummy(INT_MIN);
        ListNode *prev, *cur, *next;
        
        for (auto p = head; p; p = next) {
            next = p->next;
            // invariant: list headed by dummy.next is sorted
            for (prev = &dummy, cur = prev->next; cur && p->val > cur->val; prev = cur, cur = cur->next)
                ;
            prev->next = p;
            p->next = cur;
        }
        
        return dummy.next;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.