My C++ solution ( 24 ms) with two optimize


  • 0
    T

    Two optimize

    • compare tail node
    • compare last node

    Main Code:

    class Solution {
    public:
    
        ListNode* insertionSortList(ListNode* head) {
    
            if( head == NULL )
                return NULL;
            
            ListNode* pHead(head), *pTail(head), *pNode(NULL), *pLast(NULL);         
            head = head->next; 
            
            while( (pNode = head) != NULL)
            {
                head = head->next;
                
                if( pNode->val >= pTail->val ) // optimize a
                {
                    pTail->next = pNode;
                    pTail = pNode;
                } 
                else if( pNode->val <= pHead->val )
                {
                    pNode->next = pHead;
                    pHead = pNode;
                }
                else
                {
                    ListNode* pNode2 = (pLast != NULL) && ( pNode->val > pLast->val ) ? 
                                          pLast : pHead; // optimize b
                                          
                    while( pNode2 != pTail && pNode2->next->val < pNode->val)
                        pNode2 = pNode2->next; 
                    
                    pNode->next = pNode2->next;
                    pNode2->next = pNode;
                }
                
                pLast= pNode;
            }
            
            pTail->next = NULL;
            return pHead;
        }
    };

Log in to reply
 

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