4.Rotate List

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Description

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Solution I :

class Solution {
public:

    ListNode* rotateRight(ListNode* head, int k) {
        
        if(head == NULL) {return head;}
        
        ListNode *head1 = NULL;
        ListNode *p = head;
        int len = 0;
        while(p!=NULL){
            len = len+1;
            p=p->next;
        }
        
        int rotate = 0;
        if(k<=len){
            rotate = k;
        }
        else{
            rotate = k%len;
        }
        
        p = head;
        int fd = 0;
        fd = len - rotate;
        int i=0;
        while(i<fd){
            p = p->next;
            i++;
        }
        
        while(p!=NULL){
            ListNode *temp = new ListNode;
            temp->next = NULL;
            temp->val = p->val;
            if(head1 == NULL){
                head1 = temp;
            }
            else{
                ListNode *q = head1;
                while(q->next!=NULL){
                    q = q->next;
                }
                q->next = temp;
            }
            p = p->next;
        }
        
         p = head;
         i=0;
          while(i<fd){
            ListNode *temp = new ListNode;
            temp->next = NULL;
            temp->val = p->val;
            if(head1 == NULL){
                head1 = temp;
            }
            else{
                ListNode *q = head1;
                while(q->next!=NULL){
                    q = q->next;
                }
                q->next = temp;
            }
              i++;
              p = p->next;
        }
        
        return head1;
        
    }
};

This solution has Time Complexity of O(n) but uses an extra Space Complexity of O(n)

Solution II :

Rotate in place using 2 Pointers

class Solution
{
public:
    ListNode *rotateRight(ListNode *head, int k)
    {

        if (head == NULL)
        {
            return head;
        }

        int rotate = 0;
        int len = 0;
        ListNode *p = head;
        
        while (p != NULL)
        {
            len = len + 1;
            p = p->next;
        }

        rotate = k % len;

        ListNode *q = NULL;
        p = head;
        int i = 0;
        int move = len - rotate;
        
        while (i < move)
        {
            q = p;
            p = p->next;
            i++;
        }

        if (rotate != 0)
        {
            while (p->next != NULL)
            {
                p = p->next;
            }
            p->next = head;
            head = q->next;
            q->next = NULL;
        }
        return head;
    }
};

This solution has a Time Complexity of O(n) but uses an extra Space Complexity of O(1).