A c++ solution with explaintion.


  • 0
    ListNode* insertionSortList(ListNode* head) {
            if(head==NULL || head->next==NULL) return head;
            
            ListNode* orderedHead=head, *orderedTail=head, *cur=head->next, *curNext=cur->next;
            orderedTail->next=NULL;//core concept: maintain a ordered list called 'orderedHead'---the answer.
            
            //traverse 2th node to the end.
            while(cur){
                //1.0 insert
                ListNode* p=orderedHead, *prev=0;
                bool finishInsert=false;
                while(p){
                    if(p->val > cur->val){
                        if(p==orderedHead){
                            cur->next=p;
                            orderedHead=cur;
                        }else{
                            cur->next=p;
                            prev->next=cur;
                        }
                        finishInsert=true;
                    }
                    if(finishInsert) break;
                    prev=p; p=p->next;//move to next node
                }
                if(!finishInsert){
                    orderedTail=orderedTail->next=cur;
                    orderedTail->next=NULL;
                }
                
                //2.0 move to next
                if(curNext==NULL) break;//when the next node is NULL, end while.
                cur=curNext;
                curNext=curNext->next;
            }
            
            return orderedHead;
        }

Log in to reply
 

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