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.
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 codeif __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( "Rotated by blocks Linked list ") printList(head) # This code is contributed by rutvik_56 |
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) where n is no of node in given linked list
Please refer complete article on Rotate Linked List block wise for more details!
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
