Удалить дубликаты из двусвязного списка

Question

Здравствуйте, я наткнулся на следующий вопрос. Вы дали несортированный двусвязный список. Вы должны найти и удалить дубликаты из двусвязного списка.

Каков наилучший способ сделать это с минимальной алгоритмической сложностью?

Спасибо.

Answer 1

Если места достаточно, и вам нужно действительно оптимизировать его со временем, возможно, вы можете использовать Hashset (или эквивалент в C ++).Вы читаете каждый элемент и помещаете его в хэш-набор.Если хэш-сет сообщает о дубликате, это означает, что есть дубликат.Вы просто удалили бы этот узел.

Сложность O(n)

Answer 2

Думайте об этом как о двух односвязных списках вместо одного двусвязного списка, с одним набором ссылок, идущим с первого по последний, а другим набором с последнего на первый. Вы можете отсортировать второй список с помощью сортировки слиянием, которая будет O (n log n). Теперь просмотрите список, используя первую ссылку. Для каждого узла проверьте, если (node.back)->key==node.key, и если это так, удалите его из списка. Восстановите обратный указатель во время этого обхода, чтобы список снова был правильно связан дважды.

Это не обязательно самый быстрый метод, но он не использует дополнительное пространство.

Answer 3

Предполагая, что потенциальный работодатель верит в библиотеку C ++:

// untested O(n*log(n))
temlate <class T>
void DeDup(std::list<T>& l) {
    std::set<T> s(l.begin(), l.end());
    std::list<T>(s.begin(), s.end()).swap(l);
}

Answer 4

с минимальной сложностью? Просто пройдите список до X раз (где X - количество элементов), начиная с заголовка, а затем удалите (и переназначьте указатели) вниз по списку. O (n log n) (я считаю) время в худшем случае и действительно легко кодируется.