Don't foget to exit early if you can ( 8ms C++ Soln. with explanation)


  • 0
    A

    I am seeing a lot of people not considering the early exit scenarios.
    After the modulo operation check to see if the result is zero and bail out early if no rotation is needed.

    ListNode* rotateRight(ListNode* head, int k) {

        if(!head || !(head->next) || k==0)
            return head;
        
        ListNode* temp = head;
        ListNode* prev = nullptr;
        int nodeCount =1; 
        
        // Find the total number of nodes 
        // and a pointer to the tail of the list 
        while(temp->next)
        {
            nodeCount++;
            temp = temp->next;
        }
        
        // The effect of rotating more than 
        // the nodeCount is modulo.  
        // Make a case of early exit if the result is 0 - no rotation needed. 
        if(!(k= k%nodeCount))
            return head;
        
        // Now make it a circular list
        temp->next = head;
        
        // Rotating k times has the same effect
        // as making the (nodeCout-k +1)th element as the head
        int skipCount = nodeCount - k;
        temp = head;
        
        for(int i=0;i<skipCount;++i)
        {
            prev = temp;
            temp = temp->next;
        }
        
        head = temp;
        
        // Sever the circular list 
        prev->next = nullptr;
        
        return head; 
    }

  • 0
    V

    Why do you need prev? You can simplify after making the circular list

        temp->next = head;
        k = k%nodeCount;
        for(int i=0; i<nodeCount-k; i++)
            temp = temp->next;
        head = temp->next;
        temp->next = nullptr;
        return head;
    

Log in to reply
 

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