My C++ codes (three versions provided)


  • 1
    D
           ListNode *insertionSortList(ListNode *head) {
                
         //--- Version 1, At each step, insert a new node to the sorted part of the list
                ListNode *lastSorted, *firstUnsorted, *preNode, *tempNode, *curNode;
                if(!head || !(head->next))
                {// if the list is empty or only has one node, then return
                    return head;
                }
                else
                {
                    lastSorted = head;// last node of the sorted part, it always holds that lastSorted->next is firstUnsorted
                    firstUnsorted = lastSorted->next; // the first unsorted node
                    
                    while(firstUnsorted) 
                    {// if there is still some unsorted node, first find the insertion place
                        preNode = NULL;
                        curNode = head;
                        while(curNode && (curNode->val<firstUnsorted->val))
                        {
                            preNode = curNode;
                            curNode = curNode->next;
                        }
                        if(!preNode)
                        {// if the insertion place is at the beginning, link it before the head and update head, firstUnsorted
                            tempNode = firstUnsorted->next;
                            firstUnsorted->next = head;
                            head = firstUnsorted;
                            firstUnsorted = tempNode;
                            lastSorted->next = firstUnsorted;
                        }
                        else if(curNode == firstUnsorted)
                        {// if it is the last node of the sorted part, then just update lastSorted/firstUnsorted pointers
                            lastSorted = firstUnsorted;
                            firstUnsorted = lastSorted->next;
                        }
                        else
                        { // else in the middle of the sorted part, insert it and update lastSorted/firstUnsorted pointers
                            tempNode = firstUnsorted->next;
                            preNode->next = firstUnsorted;
                            firstUnsorted->next = curNode;
                            firstUnsorted = tempNode;
                            lastSorted->next = firstUnsorted;
                        }//if
                    }// while
                    return head;
                }//if  
            }// function
       
        /*------------------------------------- Version 2, At each step, get the head node of the input list and insert to     ListNode *headNew, *curNode, *preNode, *tempNode;
                if(!head || !(head->next))
                {
                    return head;
                }
                else
                {
                    headNew = head;
                    head = head->next;
                    headNew->next = NULL;
                    
                    while(head)
                    {
                        curNode = headNew;
                        preNode = NULL;
                        while( curNode && (curNode->val < head->val))
                        {
                            preNode = curNode;
                            curNode = curNode->next;
                        }
                        if(preNode)
                        {
                            preNode->next = head;
                            tempNode = head->next;
                            head->next = curNode;
                            head = tempNode;
                        }
                        else
                        {
                            tempNode = head->next;
                            head->next = curNode;
                            headNew = head;
                            head = tempNode;
                        }
        
                    }
                    return headNew;
                }// if
        ------------------------------------------------------------------------------------------------------------------ */
        
    //  Version 3 , Selection Sorting, select the minimum element of the remaining list and insert it to a new list  at each step
    
     /*        ListNode *newHead = NULL,*newTail = NULL, *preNode, *preminNode, *curNode,*minNode;
                if(!head || !(head->next) )
                { // if the list is empty or only has one node
                    return head;
                }
                else
                {
                    while(head) // go through all the nodes in the list
                    {
                        // find the minimum node
                        curNode = head->next;
                        minNode = head;
                        preNode = head;
                        while(curNode)
                        {
                            if(curNode->val < minNode->val)
                            {
                                preminNode = preNode;
                                minNode = curNode;
                            }
                            preNode = curNode;
                            curNode = curNode->next;
                        }
                        //remove minNode from the original list
                        if(minNode == head)
                        {
                            head = minNode->next;
                        }
                        else
                        {
                            preminNode->next = minNode->next;
                        }
                        
                        // link to the new list
                        if(!newHead)
                        {
                            newHead = newTail = minNode;
                        }
                        else
                        {
                            newTail->next = minNode;
                            newTail = minNode;
                        }
                    }
                    newTail->next = NULL;
                    return newHead; 
                }//if 
       -----------------------------------------------------------------------------------------------------------------------------     */

Log in to reply
 

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