Dada una lista enlazada de longitud n y longitud de bloque k , gire de manera circular hacia la derecha/izquierda cada bloque por un número d . Si d es positivo, gire hacia la derecha, de lo contrario, gire hacia la izquierda.
Ejemplos:
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.
Requisito previo: Rotar una lista enlazada
La idea es si el valor absoluto de d es mayor que el valor de k, entonces rotar la lista de enlaces d % k veces. Si d es 0, no es necesario rotar la lista enlazada en absoluto.
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 code
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);
}
Producción:
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
¡ Consulte el artículo completo sobre Rotar lista enlazada en bloques para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA