1.
Introduction
2.
Problem Statement
2.1.
Sample Examples
3.
Approach
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
4.1.
Which parameter decides the rotation direction of the linked list?
4.2.
What is the Space complexity of this approach?
4.3.
What if the value of the degree of rotation is 0?
4.4.
What if the absolute value of the degree of rotation is larger than the value of k?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Rotate Linked List Block Wise

## Introduction

This blog covers a linked list problem. Linked lists are one of the most essential and often asked data structures in programming contests and technical interviews. There are various standard linked list problems and techniques. This blog tackles a coding task that explores how to rotate linked list block wise.

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm

## Problem Statement

A Linked List with length n and block length k is given to us. Each block must be rotated in a circular motion to the right or left by a number d. If d is positive, it should be rotated to the right. Otherwise, it should be rotated to the left. n%k == 0 holds true in all test cases.

### Sample Examples

Input

1->2->3->4->5->6->7->8->9->10->11->12->13->14->15

k = 3

d = 1

Output

3->1->2->6->4->5->9->7->8->12->10->11->15->13->14

Explanation

As the degree of rotation is positive, blocks of size 3 are rotated to the right by one.

Input

1->2->3->4->5->6

k = 2

d = 1

Output

2->1->4->3->6->5

Explanation

As the degree of rotation is positive, blocks of size 2 are rotated to the right by one.

## 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;

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)

// Clockwise Rotation
if (d > 0)
{
for (int i = 1; temp->next->next && i < k - 1; i++)
temp = temp->next;
*tail = temp;
return rotateOneBlock(tailOfBlock, temp, d - 1, tail, k);
}

// Anti-Clockwise Rotation
if (d < 0)
{
}
}

// Function for block-wise rotation of linked list
Node *blockWiseRotate(Node *head, int k, int d)
{

// if degree of rotation is 0, return head
if (d == 0)

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)
else

/* Attach the new head of next block to
the tail of this block */
tail->next = blockWiseRotate(nextBlock, k, d % k);

}

/* Utility Functions */
{
Node *new_node = new Node;
new_node->x = new_x;
}

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()
{
// 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)

cout << "The given linked list \n";

/* k is block size and d is the number of
rotations in every block.*/
int k = 3, d = 1;

cout << "\nBlock-wise rotated linked list: \n";

return 0;
}``````

Output

``````The given linked list:
1->2->3->4->5->6->7->8->9->10->11->12->13->14->15

3->1->2->6->4->5->9->7->8->12->10->11->15->13->14``````

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

### 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 AlgorithmsCompetitive ProgrammingJavaScriptSystem 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 problemsinterview 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!

Live masterclass