Remove Nth Node From End of List

Средняя№19на расстоянии n

Дана голова связного списка и число n. Нужно удалить n-й узел с конца, где последний — 1-й, и вернуть голову того, что осталось. Наш пример: 7 → 3 → 8 → 2, n = 4 — 4-й с конца узел — это голова 7, и ответ 3 → 8 → 2.

19 Remove Nth Node From End of ListРазбор · 1×

Пример: удалить 4-й с конца узел в 7 → 3 → 8 → 2: n равно длине списка, поэтому это голова.

nonedummy7382head
slowfastудалённый узелитоговый список

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

01/14
сначала · назад · пуск · шаг
Скорость
1function removeNthFromEnd(head, n):
2 dummy = new node whose next is head
3 fast = dummy
4 slow = dummy
5 repeat n times:
6 fast = fast.next
7 while fast.next is not none:
8 slow = slow.next
9 fast = fast.next
10 slow.next = slow.next.next
11 return dummy.next
состояние
slow
–
fast
–
историянажмите шаг, чтобы вернуться

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

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

  1. fast стартует на n узлов впереди, дальше оба идут по одному шагу, и разрыв остаётся n. Когда fast на последнем узле, slow — (n + 1)-й с конца, прямо перед удаляемым.
  2. Чтобы удалить узел, перецепляют узел перед ним. Фиктивный узел даёт такой узел даже голове, поэтому n, равное длине, не требует отдельного случая: slow просто не уходит с dummy.
  3. По той же причине ответ — dummy.next, а не head: когда удалена голова, head всё ещё указывает на неё.

Сложность

Время O(L), где L — длина списка: fast проходит его один раз, а slow идёт следом. Память O(1): два указателя и один фиктивный узел.

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

Решить на LeetCode ↗

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