Javascript Program to Rotate Linked List block wise
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!