Dada una lista doblemente enlazada, gire la lista enlazada en sentido contrario a las agujas del reloj por N Nodes. Aquí N es un número entero positivo dado y es más pequeño que el número de Nodes en la lista enlazada.
N = 2
Lista rotada:
Ejemplos:
Input : a b c d e N = 2 Output : c d e a b Input : a b c d e f g h N = 4 Output : e f g h a b c d
Preguntado en Amazon
Para rotar la lista Doblemente enlazada, necesitamos cambiar el siguiente del Node N a NULL, el siguiente del último Node al Node principal anterior y el anterior del Node principal al último Node y finalmente cambiar el encabezado al (N + 1) Node y anterior de nuevo Node principal a NULL (Anterior del Node principal en la lista doblemente enlazada es NULL)
Por lo tanto, debemos obtener tres Nodes: enésimo Node, (N + 1) Node enésimo y último Node. Recorra la lista desde el principio y deténgase en el Node N. Almacene el puntero al Node N. Podemos obtener (N+1) Node usando NthNode->next. Continúe recorriendo hasta el final y almacene el puntero en el último Node también. Finalmente, cambie los punteros como se indicó anteriormente y en la última lista rotada de impresión usando
la función PrintList.
Python3
# Node of a doubly linked list
class Node:
def __init__(self, next = None,
prev = None, data = None):
self.next = next # reference to next node in DLL
self.prev = prev # reference to previous node in DLL
self.data = data
def push(head, new_data):
new_node = Node(data = new_data)
new_node.next = head
new_node.prev = None
if head is not None:
head.prev = new_node
head = new_node
return head
def printList(head):
node = head
print("Given linked list")
while(node is not None):
print(node.data, end = " "),
last = node
node = node.next
def rotate(start, N):
if N == 0 :
return
# Let us understand the below code
# for example N = 2 and
# list = a <-> b <-> c <-> d <-> e.
current = start
# current will either point to Nth
# or None after this loop. Current
# will point to node 'b' in the
# above example
count = 1
while count < N and current != None :
current = current.next
count += 1
# If current is None, N is greater
# than or equal to count of nodes
# in linked list. Don't change the
# list in this case
if current == None :
return
# current points to Nth node. Store
# it in a variable. NthNode points to
# node 'b' in the above example
NthNode = current
# current will point to last node
# after this loop current will point
# to node 'e' in the above example
while current.next != None :
current = current.next
# Change next of last node to previous
# head. Next of 'e' is now changed to
# node 'a'
current.next = start
# Change prev of Head node to current
# Prev of 'a' is now changed to node 'e'
start.prev = current
# Change head to (N+1)th node
# head is now changed to node 'c'
start = NthNode.next
# Change prev of New Head node to None
# Because Prev of Head Node in Doubly
# linked list is None
start.prev = None
# change next of Nth node to None
# next of 'b' is now None
NthNode.next = None
return start
# Driver Code
if __name__ == "__main__":
head = None
head = push(head, 'e')
head = push(head, 'd')
head = push(head, 'c')
head = push(head, 'b')
head = push(head, 'a')
printList(head)
print("
")
N = 2
head = rotate(head, N)
printList(head)
# This code is contributed by vinayak sharma
Given linked list a b c d e Rotated Linked list c d e a b
Complejidad de tiempo: O(N) (N es el número de Nodes de la lista enlazada)
Espacio auxiliar: O(N)
Consulte el artículo completo sobre Rotar lista doblemente enlazada por N Nodes 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