単一リンクリストから重複を削除する

Question

リンクリストをそのように変更する方法はありますか？

これは、線形時間と一定のメモリ使用のために行う必要があると考えています。リストのすべての要素をHashMapに入れようとしましたが、これは一定の時間を与えていますが、線形のメモリ使用量をもたらします。

別の方法がありますか？

Answer 1

あなたは線形時間のためにそれを行うにはstream().distinct()メソッドを使用することができます。

List<String> result = list.stream() 
     .distinct() 
     .collect(Collectors.toList()); 

Answer 2

は、アルゴリズム的にそれは不可能に聞こえる（またはここで誰かが私を驚かせるでしょう）。

しかし、あなたは本当に道任意のアルゴリズム作ることなく、重複せずにリストのシミュレーションを作成することができます：それは実行することはできません

public class SimulatedNoDuplicatesList extends LinkedList { 
    private List originalList; 
    SimulatedNoDuplicatesList(List original) { 
     originalList = original; 
    } 
// override all the methods that you want to use with the old list. for example 
// @Override 
    public Object get(int i) { 
     if (!super.contains(i) && originalList.contains(i)) { 
      super.add(originalList.get(i)); 
     } 
     return super.get(i); 
    } 
}