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