[Insertion sort list] C++ O(n^2) time O(1) space solution


  • 0
        ListNode* insertionSortList(ListNode* head) {
            if(!head) return NULL;
            ListNode* pre=new ListNode(0);
            pre->next=head;
            ListNode* next=head->next;
            head->next=NULL;
            ListNode* cur=head;
            while(next){
                ListNode* ipre=pre;
                ListNode* icur=pre->next;
                ListNode* inext=next->next;
                while(icur&&icur->val<next->val) ipre=ipre->next,icur=icur->next;
                ipre->next=next;
                next->next=icur;
                next=inext;
            }
            return pre->next;
        }
    

Log in to reply
 

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