Rotate Linked List block wise

Read

Discuss

Given a Linked List of length n and block length k rotate in a circular manner towards right/left each block by a number d. If d is positive rotate towards right else rotate towards left.

Examples:

Input: 1->2->3->4->5->6->7->8->9->NULL, 
        k = 3 
        d = 1
Output: 3->1->2->6->4->5->9->7->8->NULL
Explanation: Here blocks of size 3 are
rotated towards right(as d is positive) 
by 1.
 
Input: 1->2->3->4->5->6->7->8->9->10->
               11->12->13->14->15->NULL, 
        k = 4 
        d = -1
Output: 2->3->4->1->6->7->8->5->10->11
             ->12->9->14->15->13->NULL
Explanation: Here, at the end of linked 
list, remaining nodes are less than k, i.e.
only three nodes are left while k is 4. 
Rotate those 3 nodes also by d.

Prerequisite: Rotate a linked list
The idea is if the absolute value of d is greater than the value of k, then rotate the link list by d % k times. If d is 0, no need to rotate the linked list at all.

C++

// C++ program to rotate a linked list block wise 
#include<bits/stdc++.h>
using namespace std;
 
/* Link list node */
class Node 
{ 
    public:
    int data; 
    Node* next; 
}; 
 
// Recursive function to rotate one block 
Node* rotateHelper(Node* blockHead, 
                        Node* blockTail, 
                        int d, Node** tail, 
                        int k) 
{ 
    if (d == 0) 
        return blockHead; 
 
    // Rotate Clockwise 
    if (d > 0) 
    { 
        Node* temp = blockHead; 
        for (int i = 1; temp->next->next && 
                        i < k - 1; i++) 
            temp = temp->next; 
        blockTail->next = blockHead; 
        *tail = temp; 
        return rotateHelper(blockTail, temp, 
                            d - 1, tail, k); 
    } 
 
    // Rotate anti-Clockwise 
    if (d < 0) 
    { 
        blockTail->next = blockHead; 
        *tail = blockHead; 
        return rotateHelper(blockHead->next, 
                blockHead, d + 1, tail, k); 
    } 
} 
 
// Function to rotate the linked list block wise 
Node* rotateByBlocks(Node* head, 
                                int k, int d) 
{ 
    // If length is 0 or 1 return head 
    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 this block 
    int i; 
    for (i = 1; temp->next && i < k; i++) 
        temp = temp->next; 
 
    // storing the first node of next block 
    Node* nextBlock = temp->next; 
 
    // If nodes of this block are less than k. 
    // Rotate this block also 
    if (i < k) 
        head = rotateHelper(head, temp, d % k, 
                                    &tail, i); 
    else
        head = rotateHelper(head, temp, d % k, 
                                    &tail, k); 
 
    // Append the new head of next block to 
    // the tail of this block 
    tail->next = rotateByBlocks(nextBlock, k, 
                                    d % k); 
 
    // return head of updated Linked List 
    return head; 
} 
 
/* UTILITY FUNCTIONS */
/* Function to push a node */
void push(Node** head_ref, int new_data) 
{ 
    Node* new_node = new Node; 
    new_node->data = new_data; 
    new_node->next = (*head_ref); 
    (*head_ref) = new_node; 
} 
 
/* Function to print linked list */
void printList(Node* node) 
{ 
    while (node != NULL) 
    { 
        cout << node->data << " "; 
        node = node->next; 
    } 
} 
 
/* Driver code*/
int main() 
{ 
    /* Start with the empty list */
    Node* head = NULL; 
 
    // create a list 1->2->3->4->5-> 
    // 6->7->8->9->NULL 
    for (int i = 9; i > 0; i -= 1) 
        push(&head, i); 
 
    cout<<"Given linked list \n"; 
    printList(head); 
 
    // k is block size and d is number of 
    // rotations in every block. 
    int k = 3, d = 2; 
    head = rotateByBlocks(head, k, d); 
 
    cout << "\nRotated by blocks Linked list \n"; 
    printList(head); 
 
    return (0); 
} 
 
// This is code is contributed by rathbhupendra

C

// C program to rotate a linked list block wise
#include <stdio.h>
#include <stdlib.h>
 
/* Link list node */
struct Node {
    int data;
    struct Node* next;
};
 
// Recursive function to rotate one block
struct Node* rotateHelper(struct Node* blockHead,
                          struct Node* blockTail,
                          int d, struct Node** tail,
                          int k)
{
    if (d == 0)
        return blockHead;
 
    // Rotate Clockwise
    if (d > 0) {
        struct Node* temp = blockHead;
        for (int i = 1; temp->next->next &&
                        i < k - 1; i++)
            temp = temp->next;
        blockTail->next = blockHead;
        *tail = temp;
        return rotateHelper(blockTail, temp,
                            d - 1, tail, k);
    }
 
    // Rotate anti-Clockwise
    if (d < 0) {
        blockTail->next = blockHead;
        *tail = blockHead;
        return rotateHelper(blockHead->next,
                blockHead, d + 1, tail, k);
    }
}
 
// Function to rotate the linked list block wise
struct Node* rotateByBlocks(struct Node* head,
                                 int k, int d)
{
    // If length is 0 or 1 return head
    if (!head || !head->next)
        return head;
 
    // if degree of rotation is 0, return head
    if (d == 0)
        return head;
 
    struct Node* temp = head, *tail = NULL;
 
    // Traverse upto last element of this block
    int i;
    for (i = 1; temp->next && i < k; i++)
        temp = temp->next;
 
    // storing the first node of next block
    struct Node* nextBlock = temp->next;
 
    // If nodes of this block are less than k.
    // Rotate this block also
    if (i < k)
        head = rotateHelper(head, temp, d % k,
                                    &tail, i);
    else
        head = rotateHelper(head, temp, d % k,
                                    &tail, k);
 
    // Append the new head of next block to
    // the tail of this block
    tail->next = rotateByBlocks(nextBlock, k,
                                      d % k);
 
    // return head of updated Linked List
    return head;
}
 
/* UTILITY FUNCTIONS */
/* Function to push a node */
void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
 
/* Function to print linked list */
void printList(struct Node* node)
{
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}
 
/* Driver program to test above function*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;
 
    // create a list 1->2->3->4->5->
    // 6->7->8->9->NULL
    for (int i = 9; i > 0; i -= 1)
        push(&head, i);
 
    printf("Given linked list \n");
    printList(head);
 
    // k is block size and d is number of
    // rotations in every block.
    int k = 3, d = 2;
    head = rotateByBlocks(head, k, d);
 
    printf("\nRotated by blocks Linked list \n");
    printList(head);
 
    return (0);
}

Java

// Java program to rotate a linked list block wise 
import java.util.*;
class GFG
{
 
/* Link list node */
static class Node 
{ 
    int data; 
    Node next; 
}; 
static Node tail;
   
// Recursive function to rotate one block 
static Node rotateHelper(Node blockHead, 
                        Node blockTail, 
                        int d, 
                        int k) 
{ 
    if (d == 0) 
        return blockHead; 
 
    // Rotate Clockwise 
    if (d > 0) 
    { 
        Node temp = blockHead; 
        for (int i = 1; temp.next.next!=null && 
                        i < k - 1; i++) 
            temp = temp.next; 
        blockTail.next = blockHead; 
        tail = temp; 
        return rotateHelper(blockTail, temp, 
                            d - 1,  k); 
    } 
 
    // Rotate anti-Clockwise 
    if (d < 0) 
    { 
        blockTail.next = blockHead; 
        tail = blockHead; 
        return rotateHelper(blockHead.next, 
                blockHead, d + 1,  k); 
    } 
    return blockHead;
} 
 
// Function to rotate the linked list block wise 
static Node rotateByBlocks(Node head, 
                                int k, int d) 
{ 
    // If length is 0 or 1 return head 
    if (head == null || head.next == null) 
        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 this block 
    int i; 
    for (i = 1; temp.next != null && i < k; i++) 
        temp = temp.next; 
 
    // storing the first node of next block 
    Node nextBlock = temp.next; 
 
    // If nodes of this block are less than k. 
    // Rotate this block also 
    if (i < k) 
        head = rotateHelper(head, temp, d % k, 
                                   i); 
    else
        head = rotateHelper(head, temp, d % k, 
                                    k); 
 
    // Append the new head of next block to 
    // the tail of this block 
    tail.next = rotateByBlocks(nextBlock, k, 
                                    d % k); 
 
    // return head of updated Linked List 
    return head; 
} 
 
/* UTILITY FUNCTIONS */
/* Function to push a node */
static Node push(Node head_ref, int new_data) 
{ 
    Node new_node = new Node(); 
    new_node.data = new_data; 
    new_node.next = head_ref; 
    head_ref = new_node;
    return head_ref;
     
} 
 
/* Function to print linked list */
static void printList(Node node) 
{ 
    while (node != null) 
    { 
        System.out.print(node.data + " "); 
        node = node.next; 
    } 
} 
 
/* Driver code*/
public static void main(String[] args) 
{ 
   
    /* Start with the empty list */
    Node head = null; 
 
    // create a list 1.2.3.4.5. 
    // 6.7.8.9.null 
    for (int i = 9; i > 0; i -= 1) 
        head = push(head, i); 
    System.out.print("Given linked list \n"); 
    printList(head); 
 
    // k is block size and d is number of 
    // rotations in every block. 
    int k = 3, d = 2; 
    head = rotateByBlocks(head, k, d); 
    System.out.print("\nRotated by blocks Linked list \n"); 
    printList(head); 
}
} 
 
// This code contributed by aashish1995

Python3

# Python3 program to rotate a linked
# list block wise 
 
# Link list node 
class Node:    
    def __init__(self, data):      
        self.data = data
        self.next = None
 
# Recursive function to rotate one block 
def rotateHelper(blockHead, blockTail,
                 d, tail, k):    
    if (d == 0):
        return blockHead, tail 
  
    # Rotate Clockwise 
    if (d > 0):
        temp = blockHead 
        i = 1       
        while temp.next.next != None and i < k - 1:
            temp = temp.next
            i += 1           
        blockTail.next = blockHead
        tail = temp
        return rotateHelper(blockTail, temp, 
                            d - 1, tail, k)
 
    # Rotate anti-Clockwise 
    if (d < 0):
        blockTail.next = blockHead 
        tail = blockHead
        return rotateHelper(blockHead.next, 
                            blockHead, d + 1, 
                            tail, k) 
     
# Function to rotate the linked list block wise 
def rotateByBlocks(head, k, d):
 
    # If length is 0 or 1 return head 
    if (head == None or head.next == None):
        return head
  
    # If degree of rotation is 0, return head 
    if (d == 0):
        return head 
    temp = head
    tail = None
  
    # Traverse upto last element of this block 
    i = 1   
    while temp.next != None and i < k:
        temp = temp.next
        i += 1
  
    # Storing the first node of next block 
    nextBlock = temp.next
  
    # If nodes of this block are less than k. 
    # Rotate this block also 
    if (i < k):
        head, tail = rotateHelper(head, temp, d % k, 
                                  tail, i) 
    else:
        head, tail = rotateHelper(head, temp, d % k, 
                                  tail, k) 
  
    # Append the new head of next block to 
    # the tail of this block 
    tail.next = rotateByBlocks(nextBlock, k, 
                               d % k);
  
    # Return head of updated Linked List 
    return head; 
 
# UTILITY FUNCTIONS 
# Function to push a node 
def push(head_ref, new_data):
 
    new_node = Node(new_data)
    new_node.data = new_data 
    new_node.next = (head_ref) 
    (head_ref) = new_node
    return head_ref
 
# Function to print linked list 
def printList(node):
    while (node != None):
        print(node.data, end = ' ')
        node = node.next
     
# Driver code
if __name__=='__main__':
     
    # Start with the empty list
    head = None
  
    # Create a list 1.2.3.4.5. 
    # 6.7.8.9.None 
    for  i in range(9, 0, -1):
        head = push(head, i) 
    print("Given linked list ")
    printList(head)
  
    # k is block size and d is number of 
    # rotations in every block. 
    k = 3
    d = 2
    head = rotateByBlocks(head, k, d)
  
    print("\nRotated by blocks Linked list ")
    printList(head)
  
# This code is contributed by rutvik_56

C#

// C# program to rotate a linked list block wise 
using System;
public class GFG
{
 
  /* Link list node */
  public
    class Node 
    { 
      public
        int data; 
      public
        Node next; 
    }; 
  static Node tail;
 
  // Recursive function to rotate one block 
  static Node rotateHelper(Node blockHead, 
                           Node blockTail, 
                           int d, 
                           int k) 
  { 
    if (d == 0) 
      return blockHead; 
 
    // Rotate Clockwise 
    if (d > 0) 
    { 
      Node temp = blockHead; 
      for (int i = 1; temp.next.next != null && 
           i < k - 1; i++) 
        temp = temp.next; 
      blockTail.next = blockHead; 
      tail = temp; 
      return rotateHelper(blockTail, temp, 
                          d - 1, k); 
    } 
 
    // Rotate anti-Clockwise 
    if (d < 0) 
    { 
      blockTail.next = blockHead; 
      tail = blockHead; 
      return rotateHelper(blockHead.next, 
                          blockHead, d + 1,  k); 
    } 
    return blockHead;
  } 
 
  // Function to rotate the linked list block wise 
  static Node rotateByBlocks(Node head, 
                             int k, int d) 
  { 
    // If length is 0 or 1 return head 
    if (head == null || head.next == null) 
      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 this block 
    int i; 
    for (i = 1; temp.next != null && i < k; i++) 
      temp = temp.next; 
 
    // storing the first node of next block 
    Node nextBlock = temp.next; 
 
    // If nodes of this block are less than k. 
    // Rotate this block also 
    if (i < k) 
      head = rotateHelper(head, temp, d % k, 
                          i); 
    else
      head = rotateHelper(head, temp, d % k, 
                          k); 
 
    // Append the new head of next block to 
    // the tail of this block 
    tail.next = rotateByBlocks(nextBlock, k, 
                               d % k); 
 
    // return head of updated Linked List 
    return head; 
  } 
 
  /* UTILITY FUNCTIONS */
  /* Function to push a node */
  static Node push(Node head_ref, int new_data) 
  { 
    Node new_node = new Node(); 
    new_node.data = new_data; 
    new_node.next = head_ref; 
    head_ref = new_node;
    return head_ref;
 
  } 
 
  /* Function to print linked list */
  static void printList(Node node) 
  { 
    while (node != null) 
    { 
      Console.Write(node.data + " "); 
      node = node.next; 
    } 
  } 
 
  /* Driver code*/
  public static void Main(String[] args) 
  { 
 
    /* Start with the empty list */
    Node head = null; 
 
    // create a list 1.2.3.4.5. 
    // 6.7.8.9.null 
    for (int i = 9; i > 0; i -= 1) 
      head = push(head, i); 
    Console.Write("Given linked list \n"); 
    printList(head); 
 
    // k is block size and d is number of 
    // rotations in every block. 
    int k = 3, d = 2; 
    head = rotateByBlocks(head, k, d); 
    Console.Write("\nRotated by blocks Linked list \n"); 
    printList(head); 
  }
} 
 
// This code is contributed by aashish1995 

Javascript

<script>
 
// JavaScript program to rotate a
// linked list block wise 
 
    /* Link list node */
class Node {
    constructor() {
        this.data = 0;
        this.next = null;
    }
}
 
    var tail;
 
    // Recursive function to rotate one block
    function rotateHelper(blockHead,  blockTail , d , k)
    {
        if (d == 0)
            return blockHead;
 
        // Rotate Clockwise
        if (d > 0) {
            var temp = blockHead;
            for (i = 1; temp.next.next != null &&
            i < k - 1; i++)
                temp = temp.next;
            blockTail.next = blockHead;
            tail = temp;
            return rotateHelper(blockTail, 
            temp, d - 1, k);
        }
 
        // Rotate anti-Clockwise
        if (d < 0) {
            blockTail.next = blockHead;
            tail = blockHead;
            return rotateHelper(blockHead.next, 
            blockHead, d + 1, k);
        }
        return blockHead;
    }
 
    // Function to rotate the linked list block wise
    function rotateByBlocks(head , k , d) {
        // If length is 0 or 1 return head
        if (head == null || head.next == null)
            return head;
 
        // if degree of rotation is 0, return head
        if (d == 0)
            return head;
 
var temp = head;
        tail = null;
 
        // Traverse upto last element of this block
        var i;
        for (i = 1; temp.next != null && i < k; i++)
            temp = temp.next;
 
        // storing the first node of next block
var nextBlock = temp.next;
 
        // If nodes of this block are less than k.
        // Rotate this block also
        if (i < k)
            head = rotateHelper(head, temp, d % k, i);
        else
            head = rotateHelper(head, temp, d % k, k);
 
        // Append the new head of next block to
        // the tail of this block
        tail.next = rotateByBlocks(nextBlock, k, d % k);
 
        // return head of updated Linked List
        return head;
    }
 
    /* UTILITY FUNCTIONS */
    /* Function to push a node */
    function push(head_ref , new_data) {
var new_node = new Node();
        new_node.data = new_data;
        new_node.next = head_ref;
        head_ref = new_node;
        return head_ref;
 
    }
 
    /* Function to print linked list */
    function printList(node) {
        while (node != null) {
            document.write(node.data + " ");
            node = node.next;
        }
    }
 
    /* Driver code */
     
 
        /* Start with the empty list */
var head = null;
 
        // create a list 1.2.3.4.5.
        // 6.7.8.9.null
        for (i = 9; i > 0; i -= 1)
            head = push(head, i);
        document.write("Given linked list <br/>");
        printList(head);
 
        // k is block size and d is number of
        // rotations in every block.
        var k = 3, d = 2;
        head = rotateByBlocks(head, k, d);
        document.write(
        "<br/>Rotated by blocks Linked list <br/>"
        );
        printList(head);
 
// This code contributed by gauravrajput1 
 
</script>

Output:

Given linked list 
1 2 3 4 5 6 7 8 9 
Rotated by blocks Linked list 
2 3 1 5 6 4 8 9 7

Time complexity: O(n) since using a single loop to traverse a linked list to rotate

Auxiliary Space: O(n) for call stack

If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!

Last Updated : 15 Jun, 2022

Rotate Linked List block wise

C++

C

Java

Python3

C#

Javascript

Please Login to comment...