リンクリストで重複した値を見つける（難しいものに簡単に変換）

Question

これは非常に簡単な質問のようです。インタビュアーからリンクリストの重複要素を探すように依頼されました。そして、彼は私に質問を困難にした制約のいくつかを教えてくれました。リンクされたリストを1回だけトラバースする必要があるという制約があります。

リソース

私が利用可能な唯一のリソースは、別のリンクリストです。

BONUS

あなたはそれを一度だけ通過することができれば、時間はO（N）

Q1である必要があり、

をその要素を削除します。私は、私は答えを見つけることができません解決策が存在するかどうかわからない、または私がちょうど私を混乱させていた...もしそうなら、どうすればそれが可能になるのですか？

Answer 1

あなたはそれゆえ、このスニペットは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; 
    } 

} 

で実行、これはJavaで実装されるとしたら、我々は 地図店キーと値のペアと要素がほとんど O(1)にアクセスすることができ Mapデータ構造を使用することができ、 HashMapを使用することができます