24 ms C++, clear.


  • 2
    D

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

    class Solution {
    public:
        ListNode* insertionSortList(ListNode* head) {
            ListNode dummy(0);
            dummy.next = head;
    
            if(head && head->next)
            {
                ListNode* pre = head;
                ListNode* p = head->next;
                while(p)
                {
                    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;
    
                    	//inserting
                    	pre->next = p->next;
                        p->next = pp->next;
                        pp->next = p;
                    }
                    else
                        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.