Dada una lista enlazada que tiene dos punteros en cada Node. El primero apunta al siguiente Node de la lista, sin embargo, el otro puntero es aleatorio y puede apuntar a cualquier Node de la lista. Escriba un programa que clone la lista dada en el espacio O(1), es decir, sin ningún espacio adicional.
Ejemplos:
Input : Head of the below-linked list
Output : A new linked list identical to the original list.
En las publicaciones anteriores, Set-1 y Set-2 se analizan varios métodos, y también está disponible la implementación de la complejidad del espacio O(n).
En esta publicación, implementaremos un algoritmo que no requerirá espacio adicional, como se explicó en el Conjunto 1.
A continuación se muestra el algoritmo:
- Cree la copia del Node 1 e insértela entre el Node 1 y el Node 2 en la lista enlazada original, cree una copia del 2 e insértela entre el 2 y el 3. Continúe de esta manera, agregue la copia de N después del enésimo Node
- Ahora copie el enlace aleatorio de esta manera
original->next->random= original->random->next; /*TRAVERSE TWO NODES*/
- Esto funciona porque original->siguiente no es más que una copia del original y Original->aleatorio->siguiente no es más que una copia del azar.
- Ahora restaure las listas enlazadas originales y copie de esta manera en un solo ciclo.
original->next = original->next->next;
copy->next = copy->next->next;
- Asegúrese de que original->next sea NULL y devuelva la lista clonada
A continuación se muestra la implementación.
Python
'''Python program to clone a linked list with next and arbitrary pointers'''
'''Done in O(n) time with O(1) extra space'''
class Node:
'''Structure of linked list node'''
def __init__(self, data):
self.data = data
self.next = None
self.random = None
def clone(original_root):
'''Clone a doubly linked list with random pointer'''
'''with O(1) extra space'''
'''Insert additional node after every node of original list'''
curr = original_root
while curr != None:
new = Node(curr.data)
new.next = curr.next
curr.next = new
curr = curr.next.next
'''Adjust the random pointers of the newly added nodes'''
curr = original_root
while curr != None:
curr.next.random = curr.random.next
curr = curr.next.next
'''Detach original and duplicate list from each other'''
curr = original_root
dup_root = original_root.next
while curr.next != None:
tmp = curr.next
curr.next = curr.next.next
curr = tmp
return dup_root
def print_dlist(root):
'''Function to print the doubly linked list'''
curr = root
while curr != None:
print('Data =', curr.data, ', Random =', curr.random.data)
curr = curr.next
####### Driver code #######
'''Create a doubly linked list'''
original_list = Node(1)
original_list.next = Node(2)
original_list.next.next = Node(3)
original_list.next.next.next = Node(4)
original_list.next.next.next.next = Node(5)
'''Set the random pointers'''
# 1's random points to 3
original_list.random = original_list.next.next
# 2's random points to 1
original_list.next.random = original_list
# 3's random points to 5
original_list.next.next.random = original_list.next.next.next.next
# 4's random points to 5
original_list.next.next.next.random = original_list.next.next.next.next
# 5's random points to 2
original_list.next.next.next.next.random = original_list.next
'''Print the original linked list'''
print('Original list:')
print_dlist(original_list)
'''Create a duplicate linked list'''
cloned_list = clone(original_list)
'''Print the duplicate linked list'''
print('
Cloned list:')
print_dlist(cloned_list)
'''This code is contributed by Shashank Singh'''
Original list : Data = 1, Random = 3 Data = 2, Random = 1 Data = 3, Random = 5 Data = 4, Random = 5 Data = 5, Random = 2 Cloned list : Data = 1, Random = 3 Data = 2, Random = 1 Data = 3, Random = 5 Data = 4, Random = 5 Data = 5, Random = 2
Complejidad de tiempo: O(n), donde n es el número de Nodes en la lista enlazada dada.
Espacio Auxiliar: O(1), ya que no se utiliza espacio extra. Los n Nodes que se insertan entre los Nodes ya se requerían para clonar la lista, por lo que podemos decir que no usamos ningún espacio adicional.
¡ Consulte el artículo completo sobre Clonar una lista enlazada con el puntero siguiente y aleatorio en el espacio O (1) 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