Проблема 10:
Удалить дубликаты: напишите код для удаления дубликатов из несортированного связанного списка.
Input: 2->1->2->5->1->6->5 Output: 2->1->5->6
Подход 1:
Используя подход с двумя указателями. Имея два цикла while, мы берем каждый узел и сравниваем его данные с каждым другим узлом в связанном списке. Если данные равны, мы соответствующим образом меняем указатели узлов.
Временная сложность: O(N²)
Космическая сложность: O(1)
Таким образом, приведенный выше подход требует времени O (N²) для удаления дубликатов из несортированного связанного списка. Теперь нам нужно снизить временную сложность с O(N²) до O(N).
Если мы посмотрим на наше предыдущее решение, то увидим, что для каждого узла мы проверяем, присутствует ли узел в списке в другом месте или нет. Мы можем избежать этого, имея хеш-таблицу. Для каждого узла мы проверим, присутствуют ли его данные в хеш-таблице или нет. Если данные отсутствуют, то узел появляется впервые, если данные присутствуют, то узел уже существует в связанном списке и является повторяющимся узлом.
Временная сложность: O(N)
Сложность пространства: O (количество уникальных узлов в списке)
Итак, это два подхода к удалению дубликатов из связанного списка.
Вот и все!! Мы решили вопрос!
