🖥 Задача о дубликатах в списке

Итак, задача: напишите функцию, которая принимает на вход несортированный связный список и удаляет из него все дубликаты.
Задачу можно решить как минимум 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, которое будем использовать для отслеживания уникальных значений связанного списка.

Подробнее

@python_job_interview