Представьте ситуацию:
У вас есть цепочка бусин с числами, причём бусины уже отсортированы по возрастанию:
[1] → [1] → [2] → [3] → [3] → [4] → [⊗]
Ваша задача: убрать повторяющиеся числа, чтобы каждое осталось только один раз.
После "уборки" цепочка должна выглядеть так:
[1] → [2] → [3] → [4] → [⊗]
🔗 Это связный список (Linked List): каждый элемент хранит значение и ссылку на следующий.
Формальное условие:
Дан отсортированный связный список. Удалите все дубликаты так, чтобы каждый элемент встречался ровно один раз. Верните голову (начало) очищенного списка.
Примеры:
Пример 1:
Вход: 1 → 1 → 2
Выход: 1 → 2
Пример 2:
Вход: 1 → 1 → 2 → 3 → 3
Выход: 1 → 2 → 3
Ограничения:
- Список уже отсортирован ✅
- Количество узлов: 0–300
- Значения: -100 до 100
Как думать о решении?
Простая аналогия:
Представьте, что вы идёте по цепочке с фонариком 🔦:
- Смотрите на текущую бусину
- Заглядываете на следующую
- Если числа одинаковые — "перепрыгиваете" через дубликат, соединяя текущую с той, что после него
- Если разные — просто идёте дальше
✨ Ключевая идея: нам не нужно создавать новый список — достаточно перенаправить ссылки в старом!
Решение на Java с комментариями
Сложность алгоритма
⏱️ Время
O(n)
Проходим по списку ровно один раз
💾 Память
O(1)
Используем только одну переменную current
Это оптимальное решение: быстрее не получится, ведь нужно хотя бы посмотреть на каждый элемент!
Заключение
Пример, рассмотренный в статье, можно найти по адресу:
https://github.com/ShkrylAndrei/leetcode/blob/main/src/main/java/info/shkryl/task83_removeDuplicatesFromSortedList/Solution.java