アルゴリズム体操11

Remove Duplicates from a Linked List

LinkedListのhead からスキャンしていき、重複するノードがあれば削除して重複がないLinkedListのheadを返します。

説明

以下のLinkedListが与えられとします。

データが重複する28 と 14　を削除すると、以下のLinkedListになります。

Solution

Runtime Complexity O(n)

重複するかどうかをソートされていないLinkedListをスキャンするので実行時間はO(n)となります。

Space Complexity O(n)

重複するかを見分けるために、HashSetのデータ構造を使い、重複するデータがない場合は最悪O(n)となります。

実装

removeDuplicate.java

class removeDuplicate{
  public LinkedListNode remove_duplicates(LinkedListNode head) 
  {
    if (head == null || head.next == null) {
      return head;
    }

    LinkedListNode cur = head;
    LinkedListNode prev = head;

    HashSet set = new HashSet();

    while (cur != null) {
      if (!set.contains(cur.data)) {
        set.add(cur.data);
        prev = cur;
      } else {
        prev.next = cur.next;
      }
      cur = cur.next;
    }
    return head;
  }
}

考え

アルゴリズムはシンプルで、二つのポインタを使いながら、HashSetにデータを入れていきます。
もし、ポインタ,curが重複するデータと遭遇した場合は、curのひとつ前のノードを指しているポインタ,prevを用いて
prev.next = cur.nextで重複するデータを含むノードを飛ばします。
メモリに余裕がある場合はこの様な実装で問題ないと思います。

しかし、メモリに制限がある場合は実行時間を犠牲にする必要があります。
LinkedListの順序を変更することが許可されている場合は、O（n logn）時間で並べ替えることができます。
ソート後は、全ての重複データを含むノードは隣接しているので、線形スキャンで削除できます。

もし、順序の変更が許されない場合は
LinkedList内の各ノードについて、前のノードに同じデータを含むノードがあるかスキャンすることになります。
このアルゴリズムはO（n^2）であり、余分なスペースを必要としませんが、かなり実行時間を犠牲にしています。