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.
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 w// 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 is 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
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!
