Привет, друзья. В этот вторник хочется решить что-то новое, но ненапряжное, поэтому давайте расмотрим задачу на связанные списки. С ними мы еще не работали.
Сложность: 🟢 Легкая
ℹ️ Описание
Вам дан односвязный список. Переверните список и верните его.
Список представлен следующей структурой.
class ListNode {
val: number
next: ListNode | null
}
⚠️ Ограничения
— Количество узлов в связанном списке находится в диапазоне от 1 до 5000
— Значение каждого узла находится в диапазоне от -5000 до 5000
✅ Решение
Для реализации данной задачи нам всего лишь необходимо перебрать все узлы связанного списка и поменять местами указатели на следующий и предыдущий узлы.
Посмотреть реализацию в блоге
🅾️ Оценка сложности
По времени
Сложность O(n), так как мы итерируемся по всем узлам списка.
По памяти
Сложность O(1), так как мы не выделяем дополнительную память.
#linked_list #easy