Удалить дубликаты из связанного списка в Python
Примечание. Для лиц, не являющихся участниками, эта статья также доступна по адресу https://dineshkumarkb.com/tech/deleting-duplicates-from-a-linked-list-in-python/
Постановка задачи:
Это популярный вопрос на собеседовании в Linked List, а также одно из постановлений проблемы при взломе собеседования по кодированию.
Напишите код для удаления дубликатов из несортированного связного списка.
Что такое связанный список?
Связанный список - это линейная структура данных, которая состоит из объекта узла и ссылки на следующий узел.
Односвязный список выглядит примерно так.
Чтобы создать связанный список в python, нам понадобится объект Node с двумя переменными и класс LinkedList для выполнения вставки, удаления и т. Д.
value
→ Чтобы сохранить текущее значение узлаnext
→ Чтобы сохранить ссылку на следующий объект узла
Класс LinkedList изначально имеет 2 метода.
insert_node()
→ Чтобы вставить новые значения в связанный список.display_list()
→ Для отображения элементов связанного списка.
Теперь, когда мы знаем, что делать, давайте создадим Node
class и LinkedList
class.
Вывод приведенного выше кода будет следующим.
Output: 15->80->25->32->15->35->25->
Теперь задача состоит в том, чтобы удалить дубликаты из связанного списка. Давайте определим подход к удалению дубликатов.
Подход-1:
Первый подход использует дополнительную структуру данных для хранения элементов и сравнения значений узлов при просмотре связанного списка.
- Просмотрите связанный список.
- Есть 2 переменные для отслеживания предыдущих и текущих значений.
- Сохраняйте значения из каждого узла в дополнительной структуре данных.
- Проверьте, существует ли уже значение узла в дополнительной структуре данных. Если да, назначьте предыдущий узел следующему текущему узлу, что исключает текущий узел. Другими словами, дублирующийся узел удаляется.
- Повторяйте это до тех пор, пока текущий узел не станет None.
Фрагмент кода для описанного выше подхода показан ниже.
Сложность времени: O (n)
Сложность пространства: O (n)
Почему мы выбрали dict
для хранения значений?
Мы вполне могли составить список для этого сценария. Однако выбор списка увеличит временную сложность delete_duplicates
метода. Причина в том, что временная сложность использования оператораin
в списке равна O(n).
И мы уже просматриваем весь связанный список в поисках дубликатов. Для каждого элемента мы проверяем, присутствует ли элемент в списке
Это может привести к общей сложности как O(n²)
.
Поэтому мы выбираем dict,
для хранения значений из связанного списка. Время поиска для dict
всегда O(1)
. Чтобы быть точным, in
операция над dict
всегда O(1)
. Поскольку нам не нужны значения для ключей, мы просто присваиваем им None
.
Теперь общая временная сложность для delete_duplicates
метода составляет O(n)
. Это намного лучше, чем использование списка для хранения значений связанного списка.
Https://wiki.python.org/moin/TimeComplexity
Подход-2:
Допустим, у нас нет права использовать дополнительную структуру данных. Тогда что? У нас нет выбора. Нам нужно идти на компромисс во временной сложности.
- Инициализировать 2 указателя (текущий и бегун), чтобы отслеживать предыдущие и текущие значения узлов.
- Текущий узел используется для просмотра связанного списка.
- Узел бегуна используется для сравнения элементов в связанном списке.
Фрагмент кода для этого подхода приведен ниже.
Сложность времени: O (n²)
Сложность пространства: O (1)
Несколько замечаний:
Я всегда сбивался с толку, почему мы выполняем нулевую проверку для runner’s next во внутреннем цикле while и почему не только для runner. Причина в том, что мы сравниваем значение текущего узла со значением следующего узла бегуна.
Допустим, мы выполняем итерацию до последнего узла, т. Е. Бегуна вместо runner.next
. Как только выполнение перейдет во внутренний цикл while для предпоследнего элемента, программа выдаст ошибку «Нет типа», поскольку не будет никакого значения для runner.next.next
, если последний элемент является дубликатом. В нашем случае это верно для значения 25.
Временная сложность этого подхода составляет O(n²)
.
Полный фрагмент кода приведен ниже.
Обратите внимание, что это не единственное решение данной проблемы. Для одного и того же могут быть разные правильные решения.