Выбор ответа Junior Связные списки обновлено
Зачем фиктивный узел
Вопрос
Зачем при удалении элементов или слиянии списков заводят фиктивный узел dummy перед головой?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Чтобы голова не была особым случаем: у неё есть предыдущий. Удаление узла требует ссылки на предыдущий.
Варианты ответа
- Чтобы удаление и слияние работали за O(1) вместо O(n)
- Чтобы сборщик мусора не удалил список во время обхода
- Это требование JS: у объекта-узла должен быть предок
- Чтобы голова не была особым случаем: у неё есть предыдущийправильный ответ
Разбор
Удаление узла требует ссылки на предыдущий. У головы предыдущего нет, отсюда ветки if (head.val === x). С dummy.next = head всё единообразно, ответ это dummy.next.
- Асимптотика не меняется.
- GC тут ни при чём: пока есть ссылка на голову, список жив.
- Никакого такого требования в JS нет.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.