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<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 \n";
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 << "\nRotated by blocks Linked list \n";
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 \n");
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("\nRotated by blocks Linked list \n");
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 \n");
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("\nRotated by blocks Linked list \n");
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("\nRotated 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 \n");
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("\nRotated by blocks Linked list \n");
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>
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
Complejidad de tiempo : O (n) desde que se usa un solo ciclo para recorrer una lista vinculada para rotar
Espacio auxiliar: O(n) para pila de llamadas
Este artículo es una contribución de Chhavi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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