Table of contents
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.
Frequently Asked Questions
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

Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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.

Also read - Merge sort in linked list

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