Example 1: 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
Algorithm:
Step 1: Take 2 pointers pointing to the head pointer.
new_head = tail = head
Step 2: Get the length of the list.
Step 3: Connect the end of the list to the starting of the list, making it a loop.
Step 4: Get modulo(k, list_len) to avoid extra rotation.
Step 5: Move the tail pointer [len – k] times
Step 6: Break the loop, and point the new_head to tail -> next.
Thus getting the new head.
Let us understand with the help of an example:
Initial list:
Now we come out of the loop, then perform
new_head = tail -> next.
Now we break the loop by “tail -> next = NULL”
Our final list will look like below:
Solution in C++
#include<iostream> using namespace std; struct Node { int data; struct Node* next; }; void display_list(struct Node **head_pointer) { // take a reference to head pointer for navigation struct Node *temp = *head_pointer; while(temp != NULL) { if(temp->next != NULL) printf("%d -> ", temp->data); else printf("%d", temp->data); //navigate to next pointer temp = temp->next; } printf("\n"); } Node* rotate_k_nodes(Node* head, int k) { if(!head) return head; int len=1; // number of nodes Node *new_head, *tail; new_head=tail=head; while(tail->next) // get the number of nodes in the list { tail = tail->next; len++; } tail->next = head; // loop the link if(k %= len) { for(auto i=0; i<len-k; i++) tail = tail->next; } new_head = tail->next; tail->next = NULL; return new_head; } int main() { struct Node* result_node; struct Node* newNode; int k = 2; struct Node* list_1 = (struct Node*) malloc(sizeof(struct Node)); list_1->data = 1; newNode = (struct Node*) malloc (sizeof(struct Node)); newNode->data = 2; list_1->next = newNode; newNode = (struct Node*) malloc (sizeof(struct Node)); newNode->data = 3; list_1->next->next = newNode; newNode = (struct Node*) malloc (sizeof(struct Node)); newNode->data = 4; list_1->next->next->next = newNode; newNode = (struct Node*) malloc (sizeof(struct Node)); newNode->data = 5; list_1->next->next->next->next = newNode; list_1->next->next->next->next->next = NULL; cout<<"The entered list is = "<<endl; display_list(&list_1); result_node = rotate_k_nodes(list_1, k); cout<<"The list after rotating "<<k <<" times is = "<<endl; display_list(&result_node); }
Output:
The entered list is = 1 -> 2 -> 3 -> 4 -> 5 The list after rotating 2 times is = 4 -> 5 -> 1 -> 2 -> 3