Dada una lista enlazada ordenada, elimine todos los Nodes que tengan números duplicados (todas las ocurrencias), dejando solo los números que aparecen una vez en la lista original.
Ejemplos:
Input: 23->28->28->35->49->49->53->53 Output: 23->35 Input: 11->11->11->11->75->75 Output: empty List
Tenga en cuenta que esto es diferente de Eliminar duplicados de la lista vinculada
La idea es mantener un puntero (prev) al Node que está justo antes del bloque de Nodes que estamos buscando duplicados. En el primer ejemplo, el puntero anterior apuntaría a 23 mientras buscamos duplicados para el Node 28. Una vez que lleguemos al último Node duplicado con valor 28 ( nómbrelo puntero actual ), podemos hacer que el siguiente campo del Node anterior sea el next of current y actualice current=current.next . Esto eliminaría el bloque de Nodes con valor 28 que tiene duplicados.
Python3
# Python3 implementation for the
# above approach
# Creating node
class Node:
def __init__(self, val):
self.val = val
self.next = None
class LinkedList:
def __init__(self):
self.head = None
# Add node into beganing of linked list
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
return new_node
# Function to remove all occurrences
# of duplicate elements
def removeAllDuplicates(self, temp):
# temp is head node of linkedlist
curr = temp
# print(' print something')
head = prev = Node(None)
head.next = curr
# Here we use the same as we do in removing
# duplicates and the only extra thing is that
# we need to remove all elements
# having duplicates that we did in 30-31
while curr and curr.next:
# until the current value and next value
# are same keep updating the current value
if curr.val == curr.next.val:
while(curr and curr.next and
curr.val == curr.next.val):
curr = curr.next
# still one of duplicate values left
# so point prec to curr
curr = curr.next
prev.next = curr
else:
prev = prev.next
curr = curr.next
return head.next
# for print the linkedlist
def printList(self):
temp1 = self.head
while temp1 is not None:
print(temp1.val, end = " ")
temp1 = temp1.next
# For getting head of linkedlist
def get_head(self):
return self.head
# Driver Code
if __name__=='__main__':
llist = LinkedList()
llist.push(53)
llist.push(53)
llist.push(49)
llist.push(49)
llist.push(35)
llist.push(28)
llist.push(28)
llist.push(23)
print('Created linked list is:')
llist.printList()
print(
'Linked list after deletion of duplicates:')
head1 = llist.get_head()
#print(head1)
llist.removeAllDuplicates(head1)
llist.printList()
# This code is contributed by PRAVEEN KUMAR(IIIT KALYANI)
Producción:
List before removal of duplicates 23 28 28 35 49 49 53 53 List after removal of duplicates 23 35
Complejidad de tiempo: O (n) ¡
Consulte el artículo completo sobre Eliminar todas las ocurrencias de duplicados de una lista vinculada ordenada 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