Approach
The approach is quite straightforward. If the absolute value of d is larger than k, the list has to be rotated by d%k times. Also, the sign of d decides the direction of rotation of the linked list.
Algorithm
1. First, determine if the absolute value of d is larger than the value of k.
2. If the absolute value of d is larger than the value of k, each block of the linked list is rotated by d % k times.
3. The sign of d decides the direction of rotation. If d is positive, the list is rotated right. Otherwise, it's rotated to the left.
4. If the value of d is 0, there is no need to rotate the linked list.
Implementation in C++
// Program to rotate linked list block wise
#include <bits/stdc++.h>
using namespace std;
/* Linked list node */
class Node
{
public:
int x;
Node *next;
};
// Function to rotate a single block
Node *rotateOneBlock(Node *headOfBlock, Node *tailOfBlock, int d, Node **tail, int k)
{
if (d == 0)
return headOfBlock;
// Clockwise Rotation
if (d > 0)
{
Node *temp = headOfBlock;
for (int i = 1; temp->next->next && i < k - 1; i++)
temp = temp->next;
tailOfBlock->next = headOfBlock;
*tail = temp;
return rotateOneBlock(tailOfBlock, temp, d - 1, tail, k);
}
// Anti-Clockwise Rotation
if (d < 0)
{
tailOfBlock->next = headOfBlock;
*tail = headOfBlock;
return rotateOneBlock(headOfBlock->next, headOfBlock, d + 1, tail, k);
}
}
// Function for block-wise rotation of linked list
Node *blockWiseRotate(Node *head, int k, int d)
{
if (!head || !head->next)
return head;
// if degree of rotation is 0, return head
if (d == 0)
return head;
Node *temp = head, *tail = NULL;
// Traverse upto last element of the block
int i;
for (i = 1; temp->next && i < k; i++)
temp = temp->next;
Node *nextBlock = temp->next;
/* If nodes of this block are lesser than k.
Rotate this block also*/
if (i < k)
head = rotateOneBlock(head, temp, d % k, &tail, i);
else
head = rotateOneBlock(head, temp, d % k, &tail, k);
/* Attach the new head of next block to
the tail of this block */
tail->next = blockWiseRotate(nextBlock, k, d % k);
return head;
}
/* Utility Functions */
void nodePush(Node **head, int new_x)
{
Node *new_node = new Node;
new_node->x = new_x;
new_node->next = (*head);
(*head) = new_node;
}
void listPrinter(Node *root)
{
while (root != NULL)
{
if (root->next == NULL)
break;
// Print the value of the node.
cout << root->x << " -> ";
root = root->next;
}
if (root != NULL)
{
cout << root->x << endl;
}
}
/* Driver code*/
int main()
{
Node *head = NULL;
// create a list as
// 1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->NULL
for (int i = 15; i > 0; i -= 1)
nodePush(&head, i);
cout << "The given linked list \n";
listPrinter(head);
/* k is block size and d is the number of
rotations in every block.*/
int k = 3, d = 1;
head = blockWiseRotate(head, k, d);
cout << "\nBlock-wise rotated linked list: \n";
listPrinter(head);
return 0;
}

You can also try this code with Online C++ Compiler
Run Code
Output
The given linked list:
1->2->3->4->5->6->7->8->9->10->11->12->13->14->15
Block-wise rotated linked list:
3->1->2->6->4->5->9->7->8->12->10->11->15->13->14

You can also try this code with Online C++ Compiler
Run Code
Time Complexity
The time complexity of the above approach is O(N), where N is the number of nodes in the linked list.
As for block rotation, the list is traversed through every node.
Space Complexity
The space complexity of the above approach is O(1).
As no other data structure is used to store the node data.
Frequently Asked Questions
Which parameter decides the rotation direction of the linked list?
The degree of rotation (d) decides the direction of rotation of the linked list. If the degree of rotation is positive, it should be rotated to the right. Otherwise, it should be rotated to the left.
What is the Space complexity of this approach?
The space complexity of the above approach is O(1).
What if the value of the degree of rotation is 0?
If the value of the degree of rotation is 0, there is no need to rotate the linked list at all.
What if the absolute value of the degree of rotation is larger than the value of k?
If the absolute value of the degree of rotation is larger than the value of k, the linked list is rotated by d % k times.
Conclusion
This article extensively discussed how to rotate Linked List Block Wise and its time and space complexities.
We hope this blog has helped you improve your knowledge regarding Linked Lists. After reading about the Linked Lists, are you not feeling excited to read/explore more articles on this topic? Don't worry, Coding Ninjas has you covered. To learn, see articles on linked lists here.
Recommended Problems -
Refer to our Guided Path on Coding Ninjas Studio to upgrade yourself in Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and much more! If you want to test your proficiency in coding, you may check out the mock test series and take part in the contests hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundle for placement preparations.
Nevertheless, you may consider our paid courses to give your career an edge over others!
Do upvote our blogs if you find them helpful and engaging!
Happy Learning!