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.
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
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