Programa Java para eliminar duplicados de una lista enlazada sin clasificar

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.

// Java program to remove duplicates from 
// unsorted linked list
class LinkedList 
{
    static Node head;
    static class Node 
    {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
  
    /* Function to remove duplicates from an
       unsorted linked list */
    void remove_duplicates()
    {
        Node ptr1 = null, 
             ptr2 = null, dup = null;
        ptr1 = head;
  
        // Pick elements one by one 
        while (ptr1 != null && 
               ptr1.next != null) 
        {
            ptr2 = ptr1;
  
            /* Compare the picked element with 
               rest of the elements */
            while (ptr2.next != null) 
            {
                // 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;
                    System.gc();
                }
                else 
                    ptr2 = ptr2.next;
                }
            }
            ptr1 = ptr1.next;
        }
    }
  
    void printList(Node node)
    {
        while (node != null) 
        {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }
  
    public static void main(String[] args)
    {
        LinkedList list = new LinkedList();
        list.head = new Node(10);
        list.head.next = new Node(12);
        list.head.next.next = new Node(11);
        list.head.next.next.next = new Node(11);
        list.head.next.next.next.next = new Node(12);
        list.head.next.next.next.next.next = new Node(11);
        list.head.next.next.next.next.next.next = new Node(10);
  
        System.out.println(
               "Linked List before removing duplicates : ");
        list.printList(head);
  
        list.remove_duplicates();
        System.out.println("");
        System.out.println(
               "Linked List after removing duplicates : ");
        list.printList(head);
    }
}
// This code is contributed by Mayank Jaiswal

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.

// Java program to remove duplicates
// from unsorted linkedlist
import java.util.HashSet;
  
public class removeDuplicates 
{
    static class node 
    {
        int val;
        node next;
  
        public node(int val) 
        {
            this.val = val;
        }
    }
      
    /* Function to remove duplicates from a
       unsorted linked list */
    static void removeDuplicate(node head) 
    {
        // Hash to store seen values
        HashSet<Integer> hs = new HashSet<>();
      
        // Pick elements one by one 
        node current = head;
        node prev = null;
        while (current != null) 
        {
            int curval = current.val;
              
             // If current value is seen before
            if (hs.contains(curval)) 
            {
                prev.next = current.next;
            } 
            else 
            {
                hs.add(curval);
                prev = current;
            }
            current = current.next;
        }
  
    }
      
    // Function to print nodes in a given 
    // linked list 
    static void printList(node head) 
    {
        while (head != null) 
        {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
  
    public static void main(String[] args) 
    {
        /* The constructed linked list is:
           10->12->11->11->12->11->10*/
        node start = new node(10);
        start.next = new node(12);
        start.next.next = new node(11);
        start.next.next.next = new node(11);
        start.next.next.next.next = new node(12);
        start.next.next.next.next.next = new node(11);
        start.next.next.next.next.next.next = new node(10);
  
        System.out.println(
               "Linked list before removing duplicates :");
        printList(start);
  
        removeDuplicate(start);
  
        System.out.println(
               "Linked list after removing duplicates :");
        printList(start);
    }
}
// This code is contributed by Rishabh Mahrsee

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!