My C++ in-place solution, O(1) space, O(N^2) 29 ms time, one trick to speed up sorting


  • 2
    D

    There are two tricks here to simplify the programming

    1. use a dummy node to track the new link head;
    2. always save the last sorted val (i.e. prev). check if the current unsorted node has a value larger than "prev", if so, we just need to search the current insert position from the previous insert position (start); otherwise, let's search from the beginning (Dummy)
       class Solution {
        public:
            ListNode* insertionSortList(ListNode* head) {
                ListNode Dummy(INT_MIN); // dummy node to track the new head
                ListNode *start = &Dummy, *temp; // the insert position
                int prev = INT_MAX; // the value of the last sorted node
    
                while(head) 
                {   
                    if(prev > head->val) start = &Dummy; // if the last sorted node has a larger value than the current one, then we have to search from the beginning
                    prev = head->val;// update prev to the current node value
                    while(start->next && start->next->val <= head->val) start = start->next; // search the insert position
                    temp = start->next;
                    start->next = head;
                    head = head->next;
                    start->next->next = temp;
                }
                return Dummy.next;
            }
        };

Log in to reply
 

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