C++ 24ms solution


  • 0

    key: don't compare from the beginning of the list each time, check last end first. If current node is greater than previous inserted node, continue from that location.

    class Solution {
    public:
    ListNode* insertionSortList(ListNode* head) {
        if (head==NULL || head->next==NULL) return head;
        ListNode *newHead=head, *curNode=head->next, *temp=newHead,*nextNode;
        newHead->next = NULL;
        while(curNode!=NULL){
            nextNode = curNode->next;
            if (curNode->val<newHead->val){
                curNode->next = newHead;
                newHead=curNode;
            }
            else{
                if (temp->val >= curNode->val)
      // key: don't compare from the beginning of the list each time, check last end first
                {   
                    temp = newHead;
                }
                while (temp->next!=NULL && temp->next->val < curNode->val){
                    temp = temp->next;
                }
                if (temp->next!=NULL){
                    curNode->next = temp->next;
                    temp->next = curNode;
                }else{
                    temp->next = curNode;
                    curNode->next = NULL;
                }
            }
            curNode = nextNode;
        }
        return newHead;
    }
    };

Log in to reply
 

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