Rotate list

 Given the head of a linked list, rotate the list to the right by k places.

 

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

 Example 3:

Input: head = [0,1,2], k = 3
Output: [0,1,2]

 


method  :

1)count(c) the length of Linked list such that temp points to last node

2)Make temp->next point to head 

3)take k=k%c

4) traverse till c-k , (starting before head/last node) in list and make (c-k)th node next as head and make (c-k)th node point to NULL ) 

c++ implementation:

ListNode* rotateRight(ListNode* head, int k) 
    {
        if(head==NULL)
            return head;
        
        ListNode* temp=head;int c=1;
        while(temp->next!=NULL)
        {
            temp=temp->next;
            c++;
        }
        
        k=k%c;
        
        if(k==0)
            return head;
        
        ListNode* t=head;
        for(int i=0;i<c-k-1;i++)
        {
            t=t->next;
        }
        
        ListNode* newhead=t->next;
        t->next=NULL;
        temp->next=head;
        return newhead;
    }


Time Complexity: O(n) 
space Complexity: O(1) 


darkmode