One point should be noticed to get 24ms


  • 0

    You should skip the nodes that are sorted already. BTW. I don't create the dummy head node which I think it's better. Because making dummy head node makes the logic easier.

    class Solution {
    public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* ln=head?head->next:NULL;
        ListNode* prev=head;
        while(ln){
            // skip all of the sorted nodes, otherwise, it doubles the time.
            if(ln->val>prev->val){
                prev=ln;
                ln=ln->next;
            }
            else{
                ListNode* nxt=ln->next;
                ListNode* pp=NULL;
                ListNode* p=head;
                // traditional insertion sort.
                for(; p!=ln; p=p->next){
                    if(ln->val<p->val){
                        prev->next=ln->next;
                        pp ? pp->next=ln : head=ln;
                        ln->next=p;
                        break;
                    }
                    pp=p;
                }
                ln=nxt;
            }
        }
        return head;
    }};

Log in to reply
 

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