C++ solution with some explanations


  • 0
    K
     ListNode* rotateRight(ListNode* head, int k) {
        if(head==NULL||k==0) return head;
        //1. Get the length of the linkedlist
        ListNode* n1=head;
        int len=0;
        while(n1!=NULL){
            n1=n1->next;
            len++;
        }
        //2.Calculate the actual rotation steps s and move pointer n2 to s place from head.
        ListNode* n2=head;
        int s=k%len;
        if(s==0) return head;
        int t=s-1;
        while(t-->0){
            n2=n2->next;
        }
        //3. Move n2 and n3 until n2 is the at end of the linkedlist. Then, n3 is the  new head to return
        ListNode* n3=head;
        while(n2->next!=NULL){
            n2=n2->next;
            n3=n3->next;
        }
        n2->next=head; //"connect" the linkedlist
        //4, move pointer to make the new tail of the linked list.
        int d=len-s-1;
        ListNode* n4=head;
        while(d-->0){
            n4=n4->next;
        }
        n4->next=NULL;
        
        return n3;
    }

Log in to reply
 

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