Rotate List Leetcode Solution

The problem Rotate List Leetcode Solution provides us a linked list and an integer. We are told to rotate the linked list to the right by k places. So if we rotate a linked list k places to the right, in each step we take the last element from the list and place it in from. We repeat this until we have done k number of these operations. Let’s take a look at a few examples.

head = [1,2,3,4,5], k = 2

[4,5,1,2,3]

Explanation: Let’s break the operation into 2 simple rotation operations. So, in the first step or move, we simply take the element from the end of the list and place it in front. So, the list becomes [5, 1, 2, 3, 4]. Now, again we repeat the same operation making the list, [4, 5, 1, 2, 3]. And hence the answer.

head = [0,1,2], k = 4

[2, 0, 1]

Explanation: Repeating the process 4 times result in the answer linked list. It can be better understood by looking at the image below.

Approach for Rotate List Leetcode Solution

The problem Rotate List Leetcode Solution states that you are given a linked list with an integer for rotation. This means that we need to rotate the list k places to the right. The problem can be understood by a simple operation of taking the elements from the end of the list and placing them in front. Since there is no way to efficiently remove an element from the end and place it in front. We need to think of any other way to perform the operation. If we observe, we can see that after performing k operations, k elements from the end are removed and are placed in front. One thing to note here is, if the size of k is greater than the size of the linked list. We will take the modulo of k over the length of the linked list.

Once done, we will traverse until the kth node from the end. Then we perform some of the operations, we assign the next of the last node to the head. Assign the kth node from the end as head of the linked list. But we should not forget assigning the next node of k-1 th node from the end as null. Now, after performing these 3 operations, we have rotated the list.

Code for Rotate List Leetcode Solution

C++ code

#include <bits/stdc++.h>
using namespace std;

struct ListNode{
    int data;
    ListNode* next;
};

ListNode* rotateRight(ListNode* head, int k) {
    if(head==NULL || head->next==NULL)return head;

    ListNode *tmp = head;
    int cnt = 0;
    while(tmp)tmp=tmp->next,cnt++;
    tmp=head;
    k%=cnt;
    if(k==0)return head;

    while(k--)tmp = tmp->next;
    ListNode *tmpHead = head;
    while(tmp->next!=NULL){
        tmp = tmp->next;
        head = head->next;
    }
    ListNode* newHead = head->next;
    tmp->next = tmpHead;
    head->next = NULL;
    return newHead;
}

int main(){
    ListNode *head = new ListNode();
    head->data = 0;
    head->next = new ListNode();
    head->next->data = 1;
    head->next->next = new ListNode();
    head->next->next->data = 2;

    head = rotateRight(head, 4);
    while(head != NULL){
        cout<<head->data<<" ";
        head = head->next;
    }
}

2 0 1

Java Code

import java.util.*;
import java.lang.*;
import java.io.*;

class ListNode{
  int data;
  ListNode next;
}

class Solution {
    public static ListNode rotateRight(ListNode head, int k) {
        if(head==null || head.next==null)return head;
    
        ListNode tmp = head;
        int cnt = 0;
        while(tmp != null){
            tmp=tmp.next;
            cnt++;
        }
        tmp=head;
        k %= cnt;
        if(k==0)return head;

        while(k-- > 0)
            tmp = tmp.next;
        ListNode tmpHead = head;
        while(tmp.next != null){
            tmp = tmp.next;
            head = head.next;
        }
        ListNode newHead = head.next;
        tmp.next = tmpHead;
        head.next = null;
        return newHead;
    }
    
    public static void main(String[] args){
    	ListNode head = new ListNode();
      head.data = 0;
      head.next = new ListNode();
      head.next.data = 1;
      head.next.next = new ListNode();
      head.next.next.data = 2;
  
      head = rotateRight(head, 4);
      while(head != null){
          System.out.print(head.data + " ");
          head = head.next;
      }
    }
}

2 0 1

Complexity Analysis

Time Complexity

O(N), where N represents the size of the linked list. Since we have to traverse the linked list, the time complexity is linear and is dependent on the size of the list.

Space Complexity

O(1), since we do not need to store information for each of the nodes. Thus, space Complexity is constant.