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)となります。
実装
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)であり、余分なスペースを必要としませんが、かなり実行時間を犠牲にしています。