# Rotate a Linked List

In this article, we will solve the problem: “Rotate a Linked List”

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

Examples:

```Example 1:
Input:
k = 2
Output:
Explanation:
We have to rotate the list to the right twice. ```
```Example 2:
Input:
k = 4
Output:
Explanation: ```

Solution: Brute Force

Approach:

We have to move the last element to first for each k.

For each k, find the last element from the list. Move it to the first.

Code:

## C++ Code

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

class node {
public:
int num;
node* next;
node(int a) {
num = a;
next = NULL;
}
};
//utility function to insert node at the end of the list
void insertNode(node* &head,int val) {
node* newNode = new node(val);
if(head == NULL) {
return;
}
node* temp = head;
while(temp->next != NULL) temp = temp->next;

temp->next = newNode;
return;
}
//utility function to rotate list by k times
node* rotateRight(node* head,int k) {
for(int i=0;i<k;i++) {
node* temp = head;
while(temp->next->next != NULL) temp = temp->next;
node* end = temp->next;
temp->next = NULL;
}
}
//utility function to print list
void printList(node* head) {
while(head->next != NULL) {
}
return;
}

int main() {
node* head = NULL;
//inserting Node

cout<<"Original list: ";

int k = 2;
node* newHead = rotateRight(head,k);//calling function for rotating right of
the nodes by k times

cout<<"After "<<k<<" iterations: ";
printList(newHead);//list after rotating nodes
return 0;
}
``````

Output:

Original list: 1->2->3->4->5
After 2 iterations: 4->5->1->2->3

Time Complexity: O(Number of nodes present in the list*k)

Reason: For k times, we are iterating through the entire list to get the last element and move it to first.

Space Complexity: O(1)

Reason: No extra data structures is used for computations

## Java Code

``````import java.util.*;
class Node {
int num;
Node next;
Node(int a) {
num = a;
next = null;
}
}
class TUF {
//utility function to insert node at the end of the list
static Node insertNode(Node head, int val) {
Node newNode = new Node(val);
if (head == null) {
}
Node temp = head;
while (temp.next != null) temp = temp.next;

temp.next = newNode;
}
//utility function to rotate list by k times
static Node rotateRight(Node head, int k) {
if (head == null || head.next == null) return head;
for (int i = 0; i < k; i++) {
Node temp = head;
while (temp.next.next != null) temp = temp.next;
Node end = temp.next;
temp.next = null;
}
}
//utility function to print list
static void printList(Node head) {
while (head.next != null) {
}

}

public static void main(String args[]) {
Node head = null;
//inserting Node

System.out.println("Original list: ");

int k = 2;
Node newHead = rotateRight(head, k); //calling function for rotating
right of the nodes by k times

System.out.println("After " + k + " iterations: ");
printList(newHead); //list after rotating nodes

}
}``````

Output:

Original list:
1->2->3->4->5
After 2 iterations:
4->5->1->2->3

Time Complexity: O(Number of nodes present in the list*k)

Reason: For k times, we are iterating through the entire list to get the last element and move it to first.

Space Complexity: O(1)

Reason: No extra data structures are used for computations

Solution: Optimal Solution

Approach:

Let’s take an example.

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

If we see a brute force approach, it will take O(5*2000000000) which is not a good time complexity when we can optimize it.

We can see that for every k which is multiple of the length of the list, we get back the original list. Try to operate brute force on any linked list for k as multiple of the length of the list.

This gives us a hint that for k greater than the length of the list, we have to rotate the list for k%length of the list. This reduces our time complexity.

Steps to the algorithm:-

• Calculate the length of the list.
• Connect the last node to the first node, converting it to a circular linked list.
• Iterate to cut the link of the last node and start a node of k%length of the list rotated list.

Dry Run:

Let’s calculate the length of the list by iterating on it until it reaches null and increasing the count. Once the length is calculated we will connect the last node to the first node.

Now, the length of the list is 5 and k is 2. k is less than the length of the given list. So, we will have the head of the rotating list at the kth element from the end remove the link from the length-k node from its next node and make it NULL.

Thus, we received our desired output.

Code:

## C++ Code

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

class node {
public:
int num;
node* next;
node(int a) {
num = a;
next = NULL;
}
};
//utility function to insert node at the end of the list
void insertNode(node* &head,int val) {
node* newNode = new node(val);
if(head == NULL) {
return;
}
node* temp = head;
while(temp->next != NULL) temp = temp->next;

temp->next = newNode;
return;
}
//utility function to rotate list by k times
node* rotateRight(node* head,int k) {
//calculating length
node* temp = head;
int length = 1;
while(temp->next != NULL) {
++length;
temp = temp->next;
}
//link last node to first node
k = k%length; //when k is more than length of list
int end = length-k; //to get end of the list
while(end--) temp = temp->next;
//breaking last node link and pointing to NULL
temp->next = NULL;

}

//utility function to print list
void printList(node* head) {
while(head->next != NULL) {
}
return;
}

int main() {
node* head = NULL;
//inserting Node

cout<<"Original list: ";

int k = 2;
node* newHead = rotateRight(head,k);//calling function for rotating right of the nodes by k times

cout<<"After "<<k<<" iterations: ";
printList(newHead);//list after rotating nodes
return 0;
}
``````

Output:

Original list: 1->2->3->4->5
After 2 iterations: 4->5->1->2->3

Time Complexity: O(length of list) + O(length of list – (length of list%k))

Reason: O(length of the list) for calculating the length of the list. O(length of the list – (length of list%k)) for breaking link.

Space Complexity: O(1)

Reason: No extra data structure is used for computation.

## Java Code

``````import java.util.*;
class Node {
int num;
Node next;
Node(int a) {
num = a;
next = null;
}
}
class TUF{
//utility function to insert node at the end of the list
static Node insertNode(Node head,int val) {
Node newNode = new Node(val);
if(head == null) {
}
Node temp = head;
while(temp.next != null) temp = temp.next;

temp.next = newNode;
}
//utility function to rotate list by k times
static Node rotateRight(Node head,int k) {
//calculating length
Node temp = head;
int length = 1;
while(temp.next != null) {
++length;
temp = temp.next;
}
//link last node to first node
k = k%length; //when k is more than length of list
int end = length-k; //to get end of the list
while(end--!=0) temp = temp.next;
//breaking last node link and pointing to NULL
temp.next = null;

}

//utility function to print list
static void printList(Node head) {
while(head.next != null) {
}

}

public static void main(String args[]) {
Node head = null;
//inserting Node

System.out.println("Original list: ");

int k = 2;
Node newHead = rotateRight(head,k);//calling function for rotating right
of the nodes by k times

System.out.println("After "+k+" iterations: ");
printList(newHead);//list after rotating nodes

}
}``````

Output:

Original list:
1->2->3->4->5
After 2 iterations:
4->5->1->2->3

Time Complexity: O(length of list) + O(length of list – (length of list%k))

Reason: O(length of the list) for calculating the length of the list. O(length of the list – (length of list%k)) for breaking link.

Space Complexity: O(1)

Reason: No extra data structure is used for computation.

Special thanks to Dewanshi Paul for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article