# Rotate a Linked List

__Introduction__

__Introduction__

A linked list is a linear data structure that consists of nodes. Each Node contains a data field and a pointer to the next Node. In Linked List, unlike arrays, elements are not stored at contiguous memory locations but rather at different memory locations. The various elements in a linked list are linked together using pointers.

Linked List is one of the important topics from an interview perspective. Almost all the major companies ask questions related to Linked List in the initial stages. One of the most frequently asked questions by Top Product based companies, including Amazon, Flipkart, Adobe, Goldman Sachs, is “Rotate a Linked List.”

The problem statement is: **“****Given a Linked List and an integer ‘K.’ Rotate the Linked List by ‘K’ positions in a clockwise direction from the last node.”**

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 Codestudio before moving on to the solution.__

__Approach 1__

__Approach 1__

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__

__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 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 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 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:__

__Code:__

//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); } |

**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__

__Approach 2__

This approach to rotate 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**:

//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); } |

**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 number of nodes in linked list

**Space complexity:**O(1)

__Frequently asked Question__

__Frequently asked Question__

- 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.

2. How do I rotate a list?

To rotate a linked list, you need to move the nodes of the linked list in the clock or counter-clockwise; you can do so by moving nodes from front to back or moving nodes from back to the front of the linked list.

3. 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.

__Key Takeaways__

__Key Takeaways__

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!

If you want to solve __more problems__ like this which have been asked in the interviews, big tech giants like Amazon, Flipkart, Google, and Facebook, you can look out for interview problems at __Code Studio__.

Happy Learning!

Comments

## No comments yet

## Be the first to share what you think