Rotate 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 . None ; k is block size and d is number of rotations in every block .
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . next = None NEW_LINE DEDENT DEDENT def rotateHelper ( blockHead , blockTail , d , tail , k ) : NEW_LINE INDENT if ( d == 0 ) : NEW_LINE INDENT return blockHead , tail NEW_LINE DEDENT if ( d > 0 ) : NEW_LINE INDENT temp = blockHead NEW_LINE i = 1 NEW_LINE while temp . next . next != None and i < k - 1 : NEW_LINE INDENT temp = temp . next NEW_LINE i += 1 NEW_LINE DEDENT blockTail . next = blockHead NEW_LINE tail = temp NEW_LINE return rotateHelper ( blockTail , temp , d - 1 , tail , k ) NEW_LINE DEDENT if ( d < 0 ) : NEW_LINE INDENT blockTail . next = blockHead NEW_LINE tail = blockHead NEW_LINE return rotateHelper ( blockHead . next , blockHead , d + 1 , tail , k ) NEW_LINE DEDENT DEDENT def rotateByBlocks ( head , k , d ) : NEW_LINE INDENT if ( head == None or head . next == None ) : NEW_LINE INDENT return head NEW_LINE DEDENT if ( d == 0 ) : NEW_LINE INDENT return head NEW_LINE DEDENT temp = head NEW_LINE tail = None NEW_LINE i = 1 NEW_LINE while temp . next != None and i < k : NEW_LINE INDENT temp = temp . next NEW_LINE i += 1 NEW_LINE DEDENT nextBlock = temp . next NEW_LINE if ( i < k ) : NEW_LINE INDENT head , tail = rotateHelper ( head , temp , d % k , tail , i ) NEW_LINE DEDENT else : NEW_LINE INDENT head , tail = rotateHelper ( head , temp , d % k , tail , k ) NEW_LINE DEDENT tail . next = rotateByBlocks ( nextBlock , k , d % k ) ; NEW_LINE return head ; NEW_LINE DEDENT def push ( head_ref , new_data ) : NEW_LINE INDENT new_node = Node ( new_data ) NEW_LINE new_node . data = new_data NEW_LINE new_node . next = ( head_ref ) NEW_LINE ( head_ref ) = new_node NEW_LINE return head_ref NEW_LINE DEDENT def printList ( node ) : NEW_LINE INDENT while ( node != None ) : NEW_LINE INDENT print ( node . data , end = ' ▁ ' ) NEW_LINE node = node . next NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT head = None NEW_LINE for i in range ( 9 , 0 , - 1 ) : NEW_LINE INDENT head = push ( head , i ) NEW_LINE DEDENT print ( " Given ▁ linked ▁ list ▁ " ) NEW_LINE printList ( head ) NEW_LINE k = 3 NEW_LINE d = 2 NEW_LINE head = rotateByBlocks ( head , k , d ) NEW_LINE print ( " Rotated by blocks Linked list   " ) NEW_LINE printList ( head ) NEW_LINE DEDENT