Accepted solution (C++) with better named variables


  • 0
    E

    To implement insertion sort for linked list, well-defined variable names are very important to understand.

    Here are some keys:

    1. For the current to-be-examined node (currNode), its previous node is last node of the sorted list (lastSortedNode).
    2. For insertion, the last small node (lastSmallNode) in the sorted list needs to be identified. currNode needs to be inserted after lastSmallNode.
    3. Always check if currNode should be the new head.
    4. Move forward lastSortedNode only if lastSmallNode hits it.
    ListNode *insertionSortList(ListNode *head) {
    
        if (head == NULL || head->next == NULL)
            return head;
    
        ListNode *lastSortedNode = head;
        
        while (lastSortedNode->next != NULL)
        {
            // examine the current node
            ListNode *currNode = lastSortedNode->next;
            
            // check if currNode should be head
            if (head->val > currNode->val)
            {
                // move currNode to head
                lastSortedNode->next = currNode->next;
                currNode->next = head;
                head = currNode;
                continue;
            }
    
            ListNode *lastSmallNode = head;
            
            while (lastSmallNode->next != currNode)
            {
                // find the real last small node so that currNode can insert after it
                if (lastSmallNode->next->val > currNode->val)
                {
                    // insert after lastSmallNode
                    lastSortedNode->next = currNode->next;
                    currNode->next = lastSmallNode->next;
                    lastSmallNode->next = currNode;
                    break;
                }
    
                lastSmallNode = lastSmallNode->next;
            }
    
            // move forward lastSortedNode only lastSmallNode hits it
            if (lastSmallNode == lastSortedNode)
                lastSortedNode = lastSortedNode->next;
        }
        
        return head;
    }

Log in to reply
 

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