给定长度为n和块长度的链表 K 以循环方式向右/向左旋转每个块一个数字 D 如果 D 是正向向右旋转，否则向左旋转。
null
例如：
Input: 1->2->3->4->5->6->7->8->9->NULL, k = 3 d = 1Output: 3->1->2->6->4->5->9->7->8->NULLExplanation: Here blocks of size 3 arerotated 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 = -1Output: 2->3->4->1->6->7->8->5->10->11 ->12->9->14->15->13->NULLExplanation: 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.
先决条件： 旋转链表 如果d的绝对值大于k，则将链接列表旋转d%k次。如果d为0，则根本不需要旋转链表。
C++
// C++ program to rotate a linked list block wise #include<bits/stdc++.h> using namespace std; /* Link list node */ class Node { public : int data; Node* next; }; // Recursive function to rotate one block Node* rotateHelper(Node* blockHead, Node* blockTail, int d, Node** tail, int k) { if (d == 0) return blockHead; // Rotate Clockwise 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); } // 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 Node* rotateByBlocks(Node* head, int k, int d) { // If length is 0 or 1 return head if (!head || !head->next) return head; // if degree of rotation is 0, return head if (d == 0) return head; Node* temp = head, *tail = NULL; // Traverse upto last element of this block int i; for (i = 1; temp->next && i < k; i++) temp = temp->next; // storing the first node of next block Node* 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, &tail, i); else head = 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 */ 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; } /* Function to print linked list */ void printList(Node* node) { while (node != NULL) { cout << node->data << " " ; node = node->next; } } /* Driver code*/ int main() { /* Start with the empty list */ Node* head = NULL; // create a list 1->2->3->4->5-> // 6->7->8->9->NULL for ( int i = 9; i > 0; i -= 1) push(&head, i); cout<< "Given linked list " ; printList(head); // k is block size and d is number of // rotations in every block. int k = 3, d = 2; head = rotateByBlocks(head, k, d); cout << "Rotated by blocks Linked list " ; printList(head); return (0); } // This is code is contributed by rathbhupendra |
C
// C program to rotate a linked list block wise #include <stdio.h> #include <stdlib.h> /* Link list node */ struct Node { int data; struct Node* next; }; // Recursive function to rotate one block struct Node* rotateHelper( struct Node* blockHead, struct Node* blockTail, int d, struct Node** tail, int k) { if (d == 0) return blockHead; // Rotate Clockwise if (d > 0) { struct 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); } // 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 struct Node* rotateByBlocks( struct Node* head, int k, int d) { // If length is 0 or 1 return head if (!head || !head->next) return head; // if degree of rotation is 0, return head if (d == 0) return head; struct Node* temp = head, *tail = NULL; // Traverse upto last element of this block int i; for (i = 1; temp->next && i < k; i++) temp = temp->next; // storing the first node of next block struct Node* 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, &tail, i); else head = 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 */ void push( struct Node** head_ref, int new_data) { struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } /* Function to print linked list */ void printList( struct Node* node) { while (node != NULL) { printf ( "%d " , node->data); node = node->next; } } /* Driver program to test above function*/ int main() { /* Start with the empty list */ struct Node* head = NULL; // create a list 1->2->3->4->5-> // 6->7->8->9->NULL for ( int i = 9; i > 0; i -= 1) push(&head, i); printf ( "Given linked list " ); printList(head); // k is block size and d is number of // rotations in every block. int k = 3, d = 2; head = rotateByBlocks(head, k, d); printf ( "Rotated by blocks Linked list " ); printList(head); return (0); } |
JAVA
// Java program to rotate a linked list block wise import java.util.*; class GFG { /* Link list node */ static class Node { int data; Node next; }; static Node tail; // Recursive function to rotate one block static Node rotateHelper(Node blockHead, Node blockTail, int d, int k) { if (d == 0 ) return blockHead; // Rotate Clockwise if (d > 0 ) { Node temp = blockHead; for ( int 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 static Node rotateByBlocks(Node head, int k, int 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; Node temp = head; tail = null ; // Traverse upto last element of this block int i; for (i = 1 ; temp.next != null && i < k; i++) temp = temp.next; // storing the first node of next block Node 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 */ static Node 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; return head_ref; } /* Function to print linked list */ static void printList(Node node) { while (node != null ) { System.out.print(node.data + " " ); node = node.next; } } /* Driver code*/ public static void main(String[] args) { /* Start with the empty list */ Node head = null ; // create a list 1.2.3.4.5. // 6.7.8.9.null for ( int i = 9 ; i > 0 ; i -= 1 ) head = push(head, i); System.out.print( "Given linked list " ); printList(head); // k is block size and d is number of // rotations in every block. int k = 3 , d = 2 ; head = rotateByBlocks(head, k, d); System.out.print( "Rotated by blocks Linked list " ); printList(head); } } // This code contributed by aashish1995 |
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 code if __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 |
C#
// C# program to rotate a linked list block wise using System; public class GFG { /* Link list node */ public class Node { public int data; public Node next; }; static Node tail; // Recursive function to rotate one block static Node rotateHelper(Node blockHead, Node blockTail, int d, int k) { if (d == 0) return blockHead; // Rotate Clockwise if (d > 0) { Node temp = blockHead; for ( int 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 static Node rotateByBlocks(Node head, int k, int 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; Node temp = head; tail = null ; // Traverse upto last element of this block int i; for (i = 1; temp.next != null && i < k; i++) temp = temp.next; // storing the first node of next block Node 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 */ static Node 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; return head_ref; } /* Function to print linked list */ static void printList(Node node) { while (node != null ) { Console.Write(node.data + " " ); node = node.next; } } /* Driver code*/ public static void Main(String[] args) { /* Start with the empty list */ Node head = null ; // create a list 1.2.3.4.5. // 6.7.8.9.null for ( int i = 9; i > 0; i -= 1) head = push(head, i); Console.Write( "Given linked list " ); printList(head); // k is block size and d is number of // rotations in every block. int k = 3, d = 2; head = rotateByBlocks(head, k, d); Console.Write( "Rotated by blocks Linked list " ); printList(head); } } // This code is contributed by aashish1995 |
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 // 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 contributed by gauravrajput1 </script> |
输出：
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
本文由 切哈维 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
