Programa de Python para eliminar duplicados de una lista enlazada sin ordenar

Escriba una función removeDuplicates() que tome una lista y elimine cualquier Node duplicado de la lista. La lista no está ordenada. 
Por ejemplo, si la lista vinculada es 12->11->12->21->41->43->21, removeDuplicates() debería convertir la lista a 12->11->21->41->43.

MÉTODO 1 (Uso de dos bucles): 
Esta es la forma sencilla en la que se utilizan dos bucles. El bucle externo se usa para seleccionar los elementos uno por uno y el bucle interno compara el elemento seleccionado con el resto de los elementos. 
Gracias a Gaurav Saxena por su ayuda al escribir este código.

# Python3 program to remove duplicates
# from unsorted linked list
class Node():    
    def __init__(self, data):        
        self.data = data
        self.next = None
  
class LinkedList():    
    def __init__(self):
          
        # Head of list
        self.head = None
  
    def remove_duplicates(self):        
        ptr1 = None
        ptr2 = None
        dup = None
        ptr1 = self.head
  
        # Pick elements one by one
        while (ptr1 != None and 
               ptr1.next != None):
              
            ptr2 = ptr1
  
            # Compare the picked element with 
            # rest of the elements
            while (ptr2.next != None):
                  
                # If duplicate then delete it
                if (ptr1.data == ptr2.next.data):
                      
                    # Sequence of steps is important here
                    dup = ptr2.next
                    ptr2.next = ptr2.next.next
                else:
                    ptr2 = ptr2.next
                      
            ptr1 = ptr1.next
              
    # Function to print nodes in a 
    # given linked list 
    def printList(self):
        temp = self.head
          
        while(temp != None):
            print(temp.data, end = " ")
            temp = temp.next
              
        print()
          
# Driver code
list = LinkedList()
list.head = Node(10)
list.head.next = Node(12)
list.head.next.next = Node(11)
list.head.next.next.next = Node(11)
list.head.next.next.next.next = Node(12)
list.head.next.next.next.next.next = Node(11)
list.head.next.next.next.next.next.next = Node(10)
  
print("Linked List before removing duplicates :")
list.printList()
list.remove_duplicates()
print()
print("Linked List after removing duplicates :")
list.printList()
# This code is contributed by maheshwaripiyush9

Producción: 

Linked list before removing duplicates:
10 12 11 11 12 11 10 
Linked list after removing duplicates:
10 12 11

Complejidad del tiempo: O(n^2)

MÉTODO 2 (Uso de clasificación): 
En general, Merge Sort es el algoritmo de clasificación más adecuado para clasificar listas vinculadas de manera eficiente. 
1) Ordenar los elementos usando Merge Sort. Pronto escribiremos una publicación sobre cómo ordenar una lista enlazada. O(nLogn) 
2) Eliminar duplicados en tiempo lineal utilizando el algoritmo para eliminar duplicados en Lista enlazada ordenada. O(n) 
Tenga en cuenta que este método no conserva el orden original de los elementos.
Complejidad de tiempo: O (nLogn)

MÉTODO 3 (Usar Hashing): 
Recorremos la lista de enlaces de principio a fin. Para cada elemento recién encontrado, verificamos si está en la tabla hash: si es así, lo eliminamos; de lo contrario, lo ponemos en la tabla hash.

# Python3 program to remove duplicates 
# from unsorted linkedlist 
class Node:    
    def __init__(self, data):        
        self.data = data
        self.next = None
  
class LinkedList:    
    def __init__(self):        
        self.head = None
          
    # Function to print nodes in a  
    # given linked list 
    def printlist(self):        
        temp = self.head
          
        while (temp):
            print(temp.data, end = " ")
            temp = temp.next
              
    # Function to remove duplicates from a 
    # unsorted linked list 
    def removeDuplicates(self, head):
          
        # Base case of empty list or 
        # list with only one element
        if self.head is None or self.head.next is None:
            return head
              
        # Hash to store seen values 
        hash = set()  
  
        current = head
        hash.add(self.head.data)
  
        while current.next is not None:
            if current.next.data in hash:
                current.next = current.next.next
            else:
                hash.add(current.next.data)
                current = current.next
  
        return head
  
# Driver code 
if __name__ == "__main__":
      
    # Creating Empty list
    llist = LinkedList()
    llist.head = Node(10)
    second = Node(12)
    third = Node(11)
    fourth = Node(11)
    fifth = Node(12)
    sixth = Node(11)
    seventh = Node(10)
      
    # Connecting second and third
    llist.head.next = second
    second.next = third
    third.next = fourth
    fourth.next = fifth
    fifth.next = sixth
    sixth.next = seventh
  
    # Printing data
    print("Linked List before removing Duplicates.")
    llist.printlist()
    llist.removeDuplicates(llist.head)
    print("Linked List after removing duplicates.")
    llist.printlist()
# This code is contributed by rajataro0

Producción: 

Linked list before removing duplicates:
10 12 11 11 12 11 10 
Linked list after removing duplicates:
10 12 11

Gracias a bearwang por sugerir este método.
Complejidad de tiempo: O (n) en promedio (suponiendo que el tiempo de acceso a la tabla hash es O (1) en promedio).

¡ Consulte el artículo completo sobre Eliminar duplicados de una lista enlazada sin ordenar para obtener más detalles!