Выбор ответа Middle Связные списки обновлено
k-й с конца за один проход
Вопрос
Нужно удалить k-й узел с конца за один проход. Какой приём?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Два указателя с отставанием ровно на k шагов. Двигаем fast на k шагов вперёд, затем оба по одному.
Варианты ответа
- Два указателя с отставанием ровно на k шаговправильный ответ
- Посчитать длину, затем пройти до n - k
- Развернуть список и удалить k-й с начала
- Положить все узлы в стек и снять k штук
Разбор
Двигаем fast на k шагов вперёд, затем оба по одному. Когда fast упрётся в последний узел, slow стоит перед удаляемым (с dummy для случая удаления головы). Один проход, O(1) памяти.
- Подсчёт длины верен, но это два прохода.
- Разворот меняет список и тоже не один проход.
- Стек работает за один проход, но O(n) памяти.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.