24 ms C++, clear.

  • 2

    Idea: inserting is only necessary if p->val is smaller than val of previous node, otherwise we do nothing but keep moving.

    class Solution {
        ListNode* insertionSortList(ListNode* head) {
            ListNode dummy(0);
            dummy.next = head;
            if(head && head->next)
                ListNode* pre = head;
                ListNode* p = head->next;
                    if(p->val < pre->val)               //inserting only if necessary
                        ListNode* pp = &dummy;          //locate where to insert
                        while((pp->next->val < p->val)) //pp won't exceed pre, so no valid check
                            pp = pp->next;
                    	pre->next = p->next;
                        p->next = pp->next;
                        pp->next = p;
                        pre = p;                    	//no inserting, keep moving
                    p = pre->next;
            return dummy.next;

Log in to reply

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