Lecture 145:-Rotate List

To rotate a singly linked list by a given number of positions, you can follow these steps:

1. Find the length of the linked list.
2. Calculate the effective number of rotations (k) by taking the remainder of k divided by the length of the list. This helps to avoid unnecessary rotations.
3. Traverse the list to find the new tail node (the node just before the rotation point).
4. Update the pointers to rotate the list: connect the new tail node to the old head, update the new head, and set the next pointer of the new tail node to nullptr.

Here's a C++ implementation of rotating a linked list:

cppCopy code

#include <iostream> class Node { public: int data; Node* next; Node(int value) : data(value), next(nullptr) {} }; Node* rotateList(Node* head, int k) { if (!head || k == 0) return head; // Find the length of the linked list int length = 1; Node* current = head; while (current->next) { length++; current = current->next; } // Calculate the effective number of rotations k %= length; if (k == 0) return head; // No change needed // Find the new tail node Node* newTail = head; for (int i = 1; i < length - k; ++i) { newTail = newTail->next; } // Update pointers to rotate the list Node* newHead = newTail->next; newTail->next = nullptr; current->next = head; return newHead; } void displayList(Node* head) { while (head) { std::cout << head->data << " "; head = head->next; } std::cout << std::endl; } int main() { Node* head = new Node(1); head->next = new Node(2); head->next->next = new Node(3); head->next->next->next = new Node(4); head->next->next->next->next = new Node(5); int k = 2; std::cout << "Original List: "; displayList(head); head = rotateList(head, k); std::cout << "Rotated List: "; displayList(head); return 0; }

In this example, the rotateList function rotates the linked list by the given number of positions k. The displayList function is used to display the original and rotated lists.

The time complexity of rotating a linked list using this approach is O(n), where n is the number of nodes in the list. The space complexity is O(1).