C++ simple algorithm with explanation


  • 11
    P
    1. Enumerate through the list to find the last node, count the size along the way.
    2. Make a loop, by connection last to first
    3. Get modulo of |k/size| - avoiding extra rotation
    4. Enumerate again size-k nodes
    5. Break the loop and return new head

    code:

     ListNode *rotateRight(ListNode *head, int k) 
         {
            if(head == NULL || head->next == NULL||k==0) return head;
            
            ListNode* node = head;
            int size =1;
            
            while(node->next != NULL)
            {
                size++;
                node = node->next;
            }
            
            //loop the list
            node->next=head;
            
            //handle the case of k>size
            k = k%size;
            
            //find the node to break the loop at
            while(--size >= k)
            {
                node=node->next;
            }
            
            ListNode* first = node->next;
            node->next=NULL;
            
            return first;
        }

  • 0
    L

    novel point of view.


  • 0
    W

    Same idea to make a loop.


  • 0
    L

    I think you can test whether k is equal to 0 after "k = k%size",if yes,you can return "head" directly.


Log in to reply
 

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