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

Примечание. Для лиц, не являющихся участниками, эта статья также доступна по адресу https://dineshkumarkb.com/tech/deleting-duplicates-from-a-linked-list-in-python/

Постановка задачи:

Это популярный вопрос на собеседовании в Linked List, а также одно из постановлений проблемы при взломе собеседования по кодированию.

Напишите код для удаления дубликатов из несортированного связного списка.

Что такое связанный список?

Связанный список - это линейная структура данных, которая состоит из объекта узла и ссылки на следующий узел.

Односвязный список выглядит примерно так.

Чтобы создать связанный список в python, нам понадобится объект Node с двумя переменными и класс LinkedList для выполнения вставки, удаления и т. Д.

  1. value → Чтобы сохранить текущее значение узла
  2. next → Чтобы сохранить ссылку на следующий объект узла

Класс LinkedList изначально имеет 2 метода.

  1. insert_node() → Чтобы вставить новые значения в связанный список.
  2. 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²).

Полный фрагмент кода приведен ниже.

Обратите внимание, что это не единственное решение данной проблемы. Для одного и того же могут быть разные правильные решения.