10,3 тыс подписчиков
🖥 Задача о дубликатах в списке
Итак, задача: напишите функцию, которая принимает на вход несортированный связный список и удаляет из него все дубликаты.
Задачу можно решить как минимум 2 способами
🟡Движение по списку с использованием двух указателей
def remove_duplicates(first):
if not first:
return
nextone = first
while nextone:
runner = nextone
while runner.next:
if runner.next.val == nextone.val:
runner.next = runner.next.next
else:
runner = runner.next
nextone = nextone.next
return first
Функция remove_duplicates принимает на вход один аргумент first, в который мы передаем начало списка.
Далее создаем переменную nextone, которая инициализируется значением first. nextone используем для перемещения по списку, она указывает на текущий элемент. То есть эта переменная является первым указателем. Переменная runner — второй указатель.
🟡Метод с использованием хеш-таблицы
Этот подход к удалению дубликатов в связанном списке использует хеш-таблицу, чтобы отслеживать пройденные уникальные значения.
def remove_duplicates(list_head):
if not list_head:
return
seen = set()
current = list_head
prev = None
while current:
if current.val in seen:
prev.next = current.next
else:
seen.add(current.val)
prev = current
current = current.next
return list_head
Функция remove_duplicates принимает на вход один аргумент list_head, в который мы передаем начало списка. Она проверяет, пуст ли список. Если да, она возвращает результат и завершает работу. Если в списке содержится хотя бы один элемент, функция начинает их обрабатывать.
Далее создаем множество seen, которое будем использовать для отслеживания уникальных значений связанного списка.
1 минута
17 апреля 2024