Clear C++ solution in 19 ms


  • 0
    C
     ListNode* insertionSortList(ListNode* head) {
            if (head == NULL) return NULL;
            
            ListNode* scan = head;   // go through the list 
            ListNode* find = head;         // help to find the right spot to put in the node each time
            ListNode* find_prev = NULL;    // prev node of find node
            ListNode* sort_last = head;    // keep record of the last node in the sorted part
             
            scan = scan->next;
            while(scan){    
                if (scan->val >= sort_last->val ){
                    sort_last = scan;
                    scan = scan->next;
                }
                else{   // need to find the right place for the new unsorted node
                     find = head;    // start from the beginning
                     if (find->val > scan->val){   // need to change head
                         sort_last->next = scan->next;
                         scan->next = find;
                         head = scan;
                         scan = sort_last->next;
                         continue;
                     }
                     find = head->next;    // start from the one after the head
                     find_prev = head;
                     while(find->val < scan->val){
                         find_prev = find;
                         find = find->next;
                     }
                    // the value of scan is > find_prev , but < find
                         sort_last->next = scan->next;
                         scan->next = find;
                         find_prev->next = scan;
                         scan = sort_last->next;
                         continue;
                }
                
            }
            
            return head;
        }
    

Log in to reply
 

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