My 24ms C++ solution (one trick explained)


  • 2
    D

    The insertion sorting is quite trivial: starting from head, insert each node to the new sorted linked list.
    Step 1) find the inserting position (i.e. move cur to the position just before head)
    Step 2) insert head node in between of cur and cur->next;
    Step 3) move head to the next one
    Here, we use a dummy node to track the head of the sorted list.

    class Solution {
    public:
        ListNode* insertionSortList(ListNode* head) {
            ListNode dummy(INT_MIN), *cur=&dummy, *temp;
            while(head)
            { //go through each node in the list
                for(cur = &dummy; cur->next && cur->next->val<head->val; )  cur = cur->next; //step 1
                temp = head->next; 
                head->next = cur->next;
                cur->next =head; //step 2
                head = temp; //step 3
            }
            return dummy.next;
        }
    };
    

    The above one has ~80ms performance. One trick to optimize it is that: in the above version, every time we insert a new node, we always search the inserting position from the beginning of the sorted list (i.e. in step1 for(cur = &dummy;...) and that is not neccessary. If the new to-be-inserted node has a value larger than the value of the last inserted node, then that means the inserting position is after the inserting position found in the previous iteration, so we can use cur from the previous iteration directly. So we include

            if(cur->val>head->val) cur = &dummy; // trick, reset cur only when needed
    

    to reset cur to the start of the sorted list only when needed. This speeds up the algorithm to 24ms.

    class Solution {
    public:
        ListNode* insertionSortList(ListNode* head) {
            ListNode dummy(INT_MIN), *cur=&dummy, *temp;
            while(head)
            {
                if(cur->val>head->val) cur = &dummy; // trick, reset cur only when needed
                for(; cur->next && cur->next->val<head->val; ) 
                    cur = cur->next;
                temp = head->next; 
                head->next = cur->next;
                cur->next =head;
                head = temp;
            }
            return dummy.next;
        }
    };

Log in to reply
 

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