Remove Duplicates from Sorted List II

Средняя№82фиктивная голова

Дан отсортированный связный список. Нужно удалить каждое значение, которое встречается больше одного раза, вместе со всеми копиями, и оставить только значения, которые встречаются ровно один раз. Вернуть начало. Наш пример: 2 → 2 → 5 → 7 → 7 → 9 — ответ 5 → 9.

82 Remove Duplicates from Sorted List IIРазбор · 1×

Пример: 2 → 2 → 5 → 7 → 7 → 9: 2 и 7 повторяются, 5 и 9 — нет.

nonedummy225779
ещё не провереныcurcur.next, сравниваем / копия dupоставлены, до prevвырезаны

Фиктивный узел перед головой: если повторяется сама голова, перед ней всё равно есть узел, который можно перецепить

01/33
сначала · назад · пуск · шаг
Скорость
1function deleteDuplicates(head):
2 dummy = new node whose next is head
3 prev = dummy
4 cur = head
5 while cur is not none:
6 if cur.next is none or cur.next.val != cur.val:
7 prev = cur
8 cur = cur.next
9 else:
10 dup = cur.val
11 while cur is not none and cur.val == dup:
12 cur = cur.next
13 prev.next = cur
14 return dummy.next
состояние
prev
–
cur
–
dup
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Список отсортирован, поэтому копии одного значения стоят подряд: один взгляд на cur.next говорит, повторяется ли cur, а потом cur проходит мимо всех копий dup.
  2. prev переходит только на узел, у которого точно нет копий, поэтому prev.next = cur вырезает все копии одной ссылкой, вместе с первой.
  3. Фиктивный узел — узел перед головой, который никогда не удаляется. Здесь повторяется сама голова 2, и dummy.next просто становится 5.

Сложность

Время O(n): cur идёт только вперёд, по шагу на узел. Память O(1): два указателя и фиктивный узел.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.