Задача: написать код, удаляющий дубликаты из несортированного связного списка
![Задача: написать код, удаляющий дубликаты из несортированного связного списка](https://media.tproger.ru/uploads/2015/05/Doubly_linked_list.png)
Дополнительное задание. Как вы будете решать задачу, если запрещается использовать временный буфер?
Решение
Что бы удалить копии из связного списка, их нужно сначала найти. Для этого подойдет простая хэш-таблица. В приведенном далее решении выполняется проход по списку, каждый элемент которого добавляется в хэш-таблицу. Когда обнаруживается повторяющийся элемент, он удаляется, и цикл продолжает работу. За счет использования связного списка всю задачу можно решить за один проход.
Приведенное решение потребует O(N) времени, где N — количество элементов в связном списке.
Дополнительное ограничение: использование буфера запрещено
В этом случае мы можем реализовать цикл с помощью двух указателей: current (работает через связный список) и runner (проверяет все последующие узлы на наличие дубликатов).
Данный код требует всего O(1) пространства, но занимает O(N2) времени.
Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT – Компанию»
12К открытий12К показов