Trouver des valeurs en double dans la liste chaînée (Simple convertir en difficile)

Question

Cela semble être une question très simple. L'enquêteur m'a demandé de trouver l'élément en double dans la liste chaînée, puis il m'a dit certaines des contraintes qui ont rendu la question difficile pour moi. la contrainte est que vous devez traverser la liste chaînée une seule fois.

Ressources

La seule ressource dont je dispose est une autre liste chaînée.

BONUS

Supprimer que l'élément si vous pouvez le traverser qu'une seule fois,

Le temps doit être O (N)

Q1: Je ne trouve pas la réponse, je Je ne sais pas si la solution existe ou pas ou il me déroutait ... Si oui, comment cela peut-il être possible?

Answer 1

Vous pouvez utiliser un HashMap, si cela devait être mis en œuvre en Java, nous pourrions utiliser Map structure de données Les magasins de cartes paires clé-valeur et les éléments sont accessibles presque O(1) donc cet extrait court dans O(n)

private void removeDuplicates(final Node node) { 
    Map<Integer, Boolean> map = new HashMap<Integer, Boolean>(); 

    Node n = node; 
    Node prev = null; 
    while (n != null) { 
     if (map.get(n.data) == null) { 
      map.put(n.data, true); 
     } 
     else { 
      System.out.println("Found Duplicate of: "+n.data); 

      /*To remove duplicates. do this 
      if (n.next != null) { 
       n.data = n.next.data; 
       n.next = n.next.next; 
       continue; 
      } 
      if (prev != null) { 
       prev.next = n.next; 
      } 
      */ 
     } 
     prev = n; 
     n = n.next; 
    } 

}