Got TLE on {2,1} and {3,4,1} run well in VS


  • 0
    R

    The basic idea is:

    Loop from the head of the list, find every two adjacent node, if the former one is larger than the latter, then find from head until find a node that is not smaller than the latter node, then switch their values and insert the latter one to the back of the former one. it runs well on VS but got TLE on either of the cases:{2,1}, {3,4,1}.

    Any ideas?

    #define SWAP( a, b, c ){ c = a; a = b; b = c; }
    class Solution {
    public:
        ListNode *insertionSortList(ListNode *head) {
            
            if( head == NULL )
                return NULL;
            
            ListNode *node1 = head;
            ListNode *node2 = head -> next;
            ListNode *ptr, *temp;
            int tempVal;
            while( node2 != NULL )
            {
                if( node1 -> val > node2 -> val )
                {
                    ptr = head;
                    // Search from start to find a larger value
                    while( ptr -> val < node2 -> val )
                        ptr = ptr -> next;
                    
                    // Swap value
                    SWAP( node2 -> val, ptr -> val, tempVal );
                    
                    // Insert node in front
        			temp = node2 -> next;
        			node2 -> next = ptr -> next;
        			ptr -> next = node2;
        			node2 = temp;
                }
                else{
                    node1 = node1 -> next;
                    node2 = node2 -> next;
                }
            }
            
            return head;
        }
    };

Log in to reply
 

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