Дан односвязный список. Удалите из него n-й узел с конца (последний узел — первый с
конца) и верните голову получившегося списка.
type ListNode struct {
Val int
Next *ListNode
}
// RemoveNthFromEnd удаляет n-й с конца узел и возвращает новую голову.
func RemoveNthFromEnd(head *ListNode, n int) *ListNode
Примеры
1 → 2 → 3 → 4 → 5, n = 2 → 1 → 2 → 3 → 5
1, n = 1 → (пустой список, nil)
1 → 2, n = 2 → 2
1 → 2, n = 5 → 1 → 2 (такого узла нет — список не меняется)
Требования
- Новые узлы не создавать: остальные узлы те же, меняются только ссылки.
- Если
n < 1 или n больше длины списка, вернуть список без изменений. Не паниковать.
- Длина до 10⁶. Ожидается O(L) времени и O(1) памяти. Идеально — за один проход.
Устно: в исходной версии решения был код ниже. Что с ним не так?
func dropNthFromEnd(head *LNode, n int) *LNode {
dummy := &LNode{Nxt: head}
first, second := dummy, dummy
for i := 0; i <= n; i++ {
first = first.Nxt
}
for first != nil {
first = first.Nxt
second = second.Nxt
}
second.Nxt = second.Nxt.Nxt
return dummy.Nxt
}
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.