**Example**

For example, consider the given linked list is 1 -> 2 -> 3 -> 4 and K is 2 then the modified linked list after K rotation is 3 -> 4 -> 1-> 2. Notice that we have moved two-node from last to the front of the linked list

**Recommended:** Please solve it on Coding Ninjas Studio before moving on to the solution.

**Approach 1 - Efficiently Rotating a Linked List by K Positions**

To rotate a linked list by K position first thing that comes to mind is to move the K node from the back of the linked list to the front of the linked list, but there’s a problem in this approach if K is greater than the length of linked list then we will be moving same nodes multiple times so firstly we will check that whether K is smaller than the length of the linked list or not. If K is greater than the length of the linked list, then take the modulo of K with the length of the linked list(K%length). Now we can move K nodes from the back of the linked list to the front. But it is more complicated to find K nodes from the end than finding nodes from the front, so we will find the subtract K from the length, and now the problem changes to moving nodes from the front of the linked list to the back, i.e., left rotation of linked list.

**Algorithm**

- If the head is equal to null or ‘K’ is equal to 0, return the Linked List head.
- Create a variable that will store the length of the linked list and initialize it to 1.
- Create a temporary node that will be used to find the length of the Linked List and initialize it to head.
- Run a loop while the temporary node next is not equal to null and increase the length by 1 on each iteration
- If the length is less than ‘K,’ then update ‘K’ as ‘K’ % length ( To make ‘K’ come in a range of 0 to length).
- Update ‘K’ as length - ‘K’ (To reach (‘K’+1)th node from the end).
- If ‘K’ is equal to the length, return the head.
- Create a variable count, which will be used to reach (‘K’ + 1)th node from the end and initialize it to 1.
- Create a node current that will store the current node of the Linked List and initialize it to head.
- Run a loop while the count is less than ‘K’ and the current node is not equal to ‘NULL.’
- If the node is equal to ‘NULL.,’, then return the head of the Linked List.
- Update temp->next as head and update head as current->next and current->next as ‘NULL.’
- Finally, return the ‘HEAD’ of the Linked List.

**Code Implementation**

### C++

`//C++ program to rotate a linked list`

#include<iostream>

using namespace std;

/* Link list node */

class Node {

public:

int data;

Node* next;

};

//Function to rotate a linked list

Node *rotate(Node *head, int k) {

// Base condition.

if(head == NULL) {

return head;

}

int len = 1;

Node *temp = head;

// Calculate length of the linked list.

while(temp->next != NULL) {

temp = temp->next;

len += 1;

}

// If k is greater than k bring it inthe . Ifrange of 0 - len.

if(len < k) {

k = k % len;

}

k = len - k;

// Number of rotations are same as len so no change in LL.

if(k == len || k == 0) {

return head;

}

int count = 1;

Node *current = head;

while(count < k && current != NULL) {

current = current->next;

count += 1;

}

if(current == NULL) {

return head;

}

// Changing pointers.

temp->next = head;

head = current->next;

current->next = NULL;

return head;

}

//Function to take Linked list input

void input(Node ** head,int data)

{

Node* temp=new Node();

temp->data=data;

temp->next=(*head);

(*head)=temp;

}

//function to print linked list

void printlist(Node* head)

{

while(head!=NULL)

{

cout<<head->data<<" " ;

head=head->next;

}

cout<<endl;

}

int main()

{

//taking input for linked list

Node* head=NULL;

//Creating a linked list 1->2->3->4->5

input(&head,5);

input(&head,4);

input(&head,3);

input(&head,2);

input(&head,1);

int k=2;

cout<<"Original linked list \n";

printlist(head);

head=rotate(head,k);

cout<<"Linked list after rotation \n";

printlist(head);

}

### Java

`// Java program to rotate a linked list`

class Node {

int data;

Node next;

Node(int d) {

data = d;

next = null;

}

}

public class RotateLinkedList {

// Function to rotate a linked list

static Node rotate(Node head, int k) {

if (head == null) {

return head;

}

int len = 1;

Node temp = head;

// Calculate length of the linked list

while (temp.next != null) {

temp = temp.next;

len++;

}

// If k is greater than len, bring it within range of 0 - len

if (len < k) {

k = k % len;

}

k = len - k;

// If k is 0 or equal to len, no change in linked list

if (k == len || k == 0) {

return head;

}

int count = 1;

Node current = head;

// Find the kth node

while (count < k && current != null) {

current = current.next;

count++;

}

if (current == null) {

return head;

}

// Change pointers

temp.next = head;

head = current.next;

current.next = null;

return head;

}

// Function to print linked list

static void printList(Node head) {

while (head != null) {

System.out.print(head.data + " ");

head = head.next;

}

System.out.println();

}

public static void main(String[] args) {

Node head = new Node(5);

head.next = new Node(4);

head.next.next = new Node(3);

head.next.next.next = new Node(2);

head.next.next.next.next = new Node(1);

int k = 2;

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

printList(head);

head = rotate(head, k);

System.out.println("Linked list after rotation:");

printList(head);

}

}

### Python

`# Python program to rotate a linked list`

class Node:

def __init__(self, data):

self.data = data

self.next = None

# Function to rotate a linked list

def rotate(head, k):

if head is None:

return head

len = 1

temp = head

# Calculate length of the linked list

while temp.next is not None:

temp = temp.next

len += 1

# If k is greater than len, bring it within range of 0 - len

if len < k:

k = k % len

k = len - k

# If k is 0 or equal to len, no change in linked list

if k == len or k == 0:

return head

count = 1

current = head

# Find the kth node

while count < k and current is not None:

current = current.next

count += 1

if current is None:

return head

# Change pointers

temp.next = head

head = current.next

current.next = None

return head

# Function to print linked list

def printList(head):

while head is not None:

print(head.data, end=" ")

head = head.next

print()

# Main function

if __name__ == "__main__":

head = Node(5)

head.next = Node(4)

head.next.next = Node(3)

head.next.next.next = Node(2)

head.next.next.next.next = Node(1)

k = 2

print("Original linked list:")

printList(head)

head = rotate(head, k)

print("Linked list after rotation:")

printList(head)

### Output

```
Original linked list
1 2 3 4 5
Linked list after rotation
4 5 1 2 3
```

**Time Complexity:** O(n) where n is the number of nodes in the linked list

**Space complexity: **O(1)

**Approach 2 - Rotating a Singly Linked List by Converting to Circular Linked List**

This approach to rotating a linked list is similar to the previous one the only difference is that we will convert the singly linked list to a circular linked list and then move (length-K) nodes forward from the head node, making (length-K)th node’s next to null and next node as head.

**Code Implementation**

### C++

`//C++ program to rotate a linked list`

#include<iostream>

using namespace std;

/* Link list node */

class Node {

public:

int data;

Node* next;

};

//Function to rotate a linked list

Node *rotate(Node *head, int k) {

// Base condition.

if(head == NULL) {

return head;

}

int len = 1;

Node *temp = head;

// Calculate length of the linked list.

while(temp->next != NULL) {

temp = temp->next;

len += 1;

}

k = k % len;

// Number of rotations are same as len so no change in LL.

if(k == len || k == 0) {

return head;

}

// To make a circular linked list.

temp->next = head;

temp = head;

for(int i = 0; i < abs(len - k - 1); i++) {

temp = temp->next;

}

// Changing pointers.

head = temp->next;

temp->next = NULL;

return head;

}

//Function to take Linked list input

void input(Node ** head,int data)

{

Node* temp=new Node();

temp->data=data;

temp->next=(*head);

(*head)=temp;

}

//function to print linked list

void printlist(Node* head)

{

while(head!=NULL)

{

cout<<head->data<<" " ;

head=head->next;

}

cout<<endl;

}

int main()

{

//taking input for linked list

Node* head=NULL;

//Creating a linked list 1->2->3->4->5

input(&head,5);

input(&head,4);

input(&head,3);

input(&head,2);

input(&head,1);

int k=2;

cout<<"Original linked list \n";

printlist(head);

head=rotate(head,k);

cout<<"Linked list after rotation \n";

printlist(head);

}

### Java

`// Java program to rotate a linked list`

class Node {

int data;

Node next;

Node(int d) {

data = d;

next = null;

}

}

public class RotateLinkedList {

// Function to rotate a linked list

static Node rotate(Node head, int k) {

if (head == null) {

return head;

}

int len = 1;

Node temp = head;

// Calculate length of the linked list

while (temp.next != null) {

temp = temp.next;

len++;

}

k = k % len;

// If k is 0 or equal to len, no change in linked list

if (k == 0) {

return head;

}

// To make a circular linked list

temp.next = head;

temp = head;

// Find the (len - k - 1)th node

for (int i = 0; i < len - k - 1; i++) {

temp = temp.next;

}

// Changing pointers

head = temp.next;

temp.next = null;

return head;

}

// Function to print linked list

static void printList(Node head) {

while (head != null) {

System.out.print(head.data + " ");

head = head.next;

}

System.out.println();

}

public static void main(String[] args) {

Node head = new Node(5);

head.next = new Node(4);

head.next.next = new Node(3);

head.next.next.next = new Node(2);

head.next.next.next.next = new Node(1);

int k = 2;

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

printList(head);

head = rotate(head, k);

System.out.println("Linked list after rotation:");

printList(head);

}

}

### Python

`# Python program to rotate a linked list`

class Node:

def __init__(self, data):

self.data = data

self.next = None

# Function to rotate a linked list

def rotate(head, k):

if head is None:

return head

len = 1

temp = head

# Calculate length of the linked list

while temp.next is not None:

temp = temp.next

len += 1

k = k % len

# If k is 0, no change in linked list

if k == 0:

return head

# To make a circular linked list

temp.next = head

temp = head

# Find the (len - k - 1)th node

for i in range(len - k - 1):

temp = temp.next

# Changing pointers

head = temp.next

temp.next = None

return head

# Function to print linked list

def printList(head):

while head is not None:

print(head.data, end=" ")

head = head.next

print()

# Main function

if __name__ == "__main__":

head = Node(5)

head.next = Node(4)

head.next.next = Node(3)

head.next.next.next = Node(2)

head.next.next.next.next = Node(1)

k = 2

print("Original linked list:")

printList(head)

head = rotate(head, k)

print("Linked list after rotation:")

printList(head)

Output

```
Original linked list
1 2 3 4 5
Linked list after rotation
4 5 1 2 3
```

**Time Complexity:** O(n) where n is the number of nodes in a linked list

**Space complexity: **O(1)

## Frequently Asked Questions

### Can a linked list be circular?

Yes, a linked list can be circular in a circular linked list the last node points to the first node instead of NULL.

### How do you rotate a linked list counterclockwise?

To rotate a linked list counterclockwise, move the last node to the front by changing pointers accordingly, preserving the original order.

### What is the time complexity for rotating a linked list?

The time complexity for rotating a linked list is O(n), where n is the number of nodes in the linked list.

### What does it mean to rotate a list?

Rotating a linked list means considering a linked list as a circular structure and moving the node clock or anti-clockwise according to the requirement.

**Conclusion**

This blog discussed a very frequently asked interview problem, “Rotate a linked list.” The blog discussed two methods to solve this problem with algorithms and code in c++ if you want to master the linked list then check out this article.

If you are a beginner in coding and want to learn DSA, you can look out for our guided path for DSA, which is absolutely free!

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

To study more about Linked Lists, refer to __Applications Of Linked Lists__.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Learning!