Где применяется
1. Задача
В массиве любой элемент читается сразу по номеру позиции (индексу). Но вставка в середину дорогая: всё, что стоит после места вставки, приходится сдвигать на одну ячейку дальше. Связный список устроен наоборот. В нём нельзя сразу прочитать элемент по номеру, зато вставить или вырезать элемент можно за один шаг, если ты уже стоишь рядом с этим местом.
Массив хранит значения одним сплошным куском памяти, одно за другим. Поэтому прочитать позицию 5 можно сразу, а вставка в начало дорогая: каждый следующий элемент должен сдвинуться. Связный список хранит каждое значение в отдельном узле. Узел держит само значение и ссылку на следующий узел, и так узлы складываются в цепочку. Добавить элемент в начало можно сразу. Зато прыгнуть на позицию 5 нельзя: до неё нужно дойти по цепочке.
Позже будут приёмы посложнее: развернуть список, найти в нём петлю, слить два списка. Для них сначала нужно уметь простое: построить цепочку, пройти по ней и прочитать из неё значения. Этим урок и занимается.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи, где тебе дают голову связного списка и просят пройти по нему, чтобы прочитать значения, собрать их или построить по ходу новый список.
Иди от головы до null, удваивая число и прибавляя каждый бит.
Пройди список один раз, держа значения nums в множестве, и считай места, где начинается серия подходящих узлов.
Иди по списку, складывай значения между двумя нулями и добавляй каждую сумму в новый список.