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

Дополнительное задание. Как вы будете решать задачу, если запрещается использовать временный буфер?

Решение

Что бы удалить копии из связного списка, их нужно сначала найти. Для этого подойдет простая хэш-таблица. В приведенном далее решении выполняется проход по списку, каждый элемент которого добавляется в хэш-таблицу. Когда обнаруживается повторяющийся элемент, он удаляется, и цикл продолжает работу. За счет использования связного списка всю задачу можно решить за один проход.

Приведенное решение потребует O(N) времени, где N — количество элементов в связном списке.

Дополнительное ограничение: использование буфера запрещено

В этом случае мы можем реализовать цикл с помощью двух указателей: current (работает через связный список) и runner (проверяет все последующие узлы на наличие дубликатов).

Данный код требует всего O(1) пространства, но занимает O(N2) времени.

Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT – Компанию»