Rotate List Algorithm
The Rotate List Algorithm is a technique used in computer programming and data manipulation to rotate the elements of a list or an array by a specified number of positions. This algorithm is commonly used in situations where data needs to be cyclically shifted, such as in cryptography or in implementing certain data structures like circular buffers. The main idea behind the algorithm is to shift the elements of the list in a way that the first element becomes the last, the second element becomes the first, and so on, for a given number of rotations. The process can be performed either in a clockwise or counterclockwise direction, depending on the desired output.
There are several ways to implement the Rotate List Algorithm, each with its own trade-offs in terms of time and space complexity. One common approach is to reverse the list in three stages: first, reverse the entire list; next, reverse the elements from the beginning of the list to the specified rotation point; finally, reverse the remaining elements from the rotation point to the end of the list. Another approach involves using a temporary buffer to store the elements that need to be rotated, then copying those elements back into their new positions in the original list. Regardless of the specific implementation, the Rotate List Algorithm provides an efficient way to cyclically shift elements in a list, making it a valuable tool for a variety of applications in computer science and data manipulation.
/**
* Given a list, rotate the list to the right by k places, where k is non-negative.
* For example:
* Given 1->2->3->4->5->NULL and k = 2,
* return 4->5->1->2->3->NULL
*/
#include <iostream>
struct ListNode {
int val;
ListNode * next;
ListNode(int x) : val(x), next(NULL) {}
};
void printList(ListNode * node) {
std::cout << "List: ";
while( node ) {
std::cout << node->val << " ";
node = node->next;
}
std::cout << std::endl;
}
void insert(ListNode* & head, int data ) {
ListNode * newNode = new ListNode(data);
if ( head == nullptr ) {
head = newNode;
} else {
ListNode * curr = head;
while ( curr->next != nullptr ) {
curr = curr->next;
}
curr->next = newNode;
}
}
int length(ListNode * head) {
int count = 0;
while( head ) {
head = head->next;
++count;
}
return count;
}
ListNode* rotateRight(ListNode* head, int k) {
if ( head == nullptr || head->next == nullptr) {
return head;
}
int len = length(head);
k = k % len;
if ( k == 0) {
return head;
}
ListNode * ptr1 = head;
ListNode * ptr2 = head;
int c = 0;
while( ptr1 && c < k ) {
ptr1 = ptr1->next;
c++;
}
if (!ptr1) {
return nullptr;
}
while( ptr1 && ptr1->next != nullptr ) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
ListNode * newHead = ptr2->next;
ptr2->next = nullptr;
ptr1->next = head;
return newHead;
}
int main() {
ListNode * head = nullptr;
insert( head, 1);
insert( head, 2);
insert( head, 3);
insert( head, 4);
insert( head, 5);
printList(head);
head = rotateRight(head, 2);
printList(head);
return 0;
}
