Ya hemos discutido 2 formas diferentes de clonar una lista enlazada. En esta publicación, se analiza otro método simple para clonar una lista vinculada.
La idea es usar Hashing. A continuación se muestra el algoritmo.
- Recorra la lista enlazada original y haga una copia en términos de datos.
- Cree un mapa hash del par de valores clave con el Node de lista enlazada original y el Node de lista enlazada copiado.
- Recorra la lista enlazada original nuevamente y, utilizando el mapa hash, ajuste la referencia siguiente y aleatoria de los Nodes de la lista enlazada clonados.
A continuación se muestra la implementación del enfoque anterior.
Python3
# Python3 program to clone a linked list
# with random pointers
class Node:
def __init__(self, data):
# Node Data
self.data = data
# Node Next
self.next = None
# Node Random
self.random = None
# Dictionary
class MyDictionary(dict):
# __init__ function
def __init__(self):
super().__init__()
self = dict()
# Function to add key:value
def add(self, key, value):
# Adding Values to dictionary
self[key] = value
# Linked list class
class LinkedList:
# Linked list constructor
def __init__(self, node):
self.head = node
# Method to print the list.
def __repr__(self):
temp = self.head
while temp is not None:
random = temp.random
random_data = (random.data if
random is not None else -1)
data = temp.data
print(f"Data-{data},
Random data: {random_data}")
temp = temp.next
return ""
# Push method to put data always at
# the head in the linked list.
def push(self, data):
node = Node(data)
node.next = self.head
self.head = node
# Actual clone method which returns head
# reference of cloned linked list.
def clone(self):
# Initialize two references, one
# with original list's head.
original = self.head
clone = None
# Initialize two references, one
# with original list's head.
mp = MyDictionary()
# Traverse the original list and
# make a copy of that
# in the clone linked list
while original is not None:
clone = Node(original.data)
mp.add(original, clone)
original = original.next
# Adjusting the original
# list reference again.
original = self.head
# Traversal of original list again
# to adjust the next and random
# references of clone list using hash map.
while original is not None:
clone = mp.get(original)
clone.next = mp.get(original.next)
clone.random = mp.get(original.random)
original = original.next
# Return the head reference of the clone list.
return LinkedList(self.head)
# Driver code
# Pushing data in the linked list.
l = LinkedList(Node(5))
l.push(4)
l.push(3)
l.push(2)
l.push(1)
# Setting up random references.
l.head.random = l.head.next.next
l.head.next.random =
l.head.next.next.next
l.head.next.next.random =
l.head.next.next.next.next
l.head.next.next.next.random =
(l.head.next.next.next.next.next)
l.head.next.next.next.next.random =
l.head.next
# Making a clone of the
# original linked list.
clone = l.clone()
# Print the original and cloned
# linked list.s
print("Original linked list")
print(l)
print("Cloned linked list")
print(clone)
# This code is contributed by ashwinathappan
Producción:
Original linked list Data = 1, Random data = 3 Data = 2, Random data = 4 Data = 3, Random data = 5 Data = 4, Random data = -1 Data = 5, Random data = 2 Cloned linked list Data = 1, Random data = 3 Data = 2, Random data = 4 Data = 3, Random data = 5 Data = 4, Random data = -1 Data = 5, Random data = 2
Complejidad de tiempo: O(n)
Espacio auxiliar: O(n)
Consulte el artículo completo sobre Clonar una lista enlazada con puntero siguiente y aleatorio | Set 2 para 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