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