Dada una lista doblemente enlazada , la tarea es invertir la lista doblemente enlazada dada.
Vea los diagramas a continuación, por ejemplo.
(a) Original Doubly Linked List
(b) Reversed Doubly Linked List
Aquí hay un método simple para invertir una lista doblemente enlazada. Todo lo que tenemos que hacer es intercambiar los punteros anterior y siguiente para todos los Nodes, cambiar la anterior del encabezado (o inicio) y cambiar el puntero del encabezado al final.
Python
# Program to reverse a doubly linked list # A node of the doubly linked list class Node: # Constructor to create a new node def __init__(self, data): self.data = data self.next = None self.prev = None class DoublyLinkedList: # Constructor for empty Doubly # Linked List def __init__(self): self.head = None # Function reverse a Doubly Linked List def reverse(self): temp = None current = self.head # Swap next and prev for all nodes # of doubly linked list while current is not None: temp = current.prev current.prev = current.next current.next = temp current = current.prev # Before changing head, check for the # cases like empty list and list with # only one node if temp is not None: self.head = temp.prev # Given a reference to the head of a list # and an integer,inserts a new node on the # front of list def push(self, new_data): # 1. Allocates node # 2. Put the data in it new_node = Node(new_data) # 3. Make next of new node as head # and previous as None (already None) new_node.next = self.head # 4. change prev of head node to # new_node if self.head is not None: self.head.prev = new_node # 5. move the head to point to the # new node self.head = new_node def printList(self, node): while(node is not None): print node.data, node = node.next # Driver code dll = DoublyLinkedList() dll.push(2) dll.push(4) dll.push(8) dll.push(10) print "Original Linked List" dll.printList(dll.head) # Reverse doubly linked list dll.reverse() print "Reversed Linked List" dll.printList(dll.head) # This code is contributed by Nikhil Kumar Singh(nickzuck_007)
Producción:
Original linked list 10 8 4 2 The reversed Linked List is 2 4 8 10
Complejidad temporal: O(N), donde N denota el número de Nodes en la lista doblemente enlazada.
Espacio auxiliar: O(1)
También podemos intercambiar datos en lugar de punteros para invertir la lista doblemente enlazada. El método utilizado para invertir la array se puede utilizar para intercambiar datos. El intercambio de datos puede ser costoso en comparación con los punteros si el tamaño de los elementos de datos es mayor.
Escriba comentarios si encuentra que alguno de los códigos/algoritmos anteriores es incorrecto o encuentra mejores formas de resolver el mismo problema.
Método 2:
La misma pregunta también se puede hacer usando Stacks.
Pasos:
- Siga empujando los datos del Node en la pila. -> O(n)
- Sigue sacando los elementos y actualizando la lista doblemente enlazada
Python3
"""
Function to reverse a doubly-linked list
swap next and prev pointers for all the
nodes change prev of the head node
change head pointer
"""
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
"""
Method to reverse a Doubly-Linked List
using Stacks
"""
def reverseUsingStacks(self):
stack = []
temp = self.head
while temp is not None:
stack.append(temp.data)
temp = temp.next
# Add all the elements in the stack
# in a sequence to the stack
temp = self.head
while temp is not None:
temp.data = stack.pop()
temp = temp.next
# Popped all the elements and the
# added in the linked list,
# in a reversed order.
"""
Method to push a new item before
the head
"""
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
if self.head is not None:
self.head.prev = new_node
self.head = new_node
"""
Method to traverse the doubly-linked
list and print every node in the list
"""
def printList(self, node):
while(node is not None):
print(node.data)
node = node. next
# Driver code
dll = DoublyLinkedList()
dll.push(2)
dll.push(4)
dll.push(8)
dll.push(10)
print(
"original doubly-linked list")
dll.printList(dll.head)
# Reverse a doubly-linked list
dll.reverseUsingStacks()
print("Reversed doubly-linked list")
dll.printList(dll.head)
Producción:
Original linked list 10 8 4 2 The reversed Linked List is 2 4 8 10
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
En este método, recorremos la lista enlazada una vez y agregamos elementos a la pila, y nuevamente recorremos el conjunto para actualizar todos los elementos. El todo toma 2n tiempo, que es la complejidad temporal de O(n).
Consulte el artículo completo sobre Invertir una lista doblemente vinculada 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