Предварительное условие: односвязный список в JavaScript
Когда дан односвязный список, как мы можем изменить его? Как и в следующем примере, если входной связанный список имеет значение 1- ›2-› 3- ›4-› 5- ›NULL, можем ли мы обратить его в выходной как 5-› 4- ›3-› 2- ›1- >НУЛЕВОЙ?
Каждый узел связанного списка будет иметь два атрибута: значение и следующий, а связанный список будет иметь атрибут заголовка, хвоста и длины.
Существует два подхода к обращению односвязного списка: итеративный и рекурсивный.
Итеративный:
При итеративном подходе мы сохраняем предыдущий узел, устанавливаем следующий узел как предыдущий, пока мы посещаем каждый узел. Поскольку конец связанного списка имеет значение null, мы инициируем предыдущий узел как null.
Временная сложность вышеуказанного решения составляет O (n), а пространственная сложность - O (1).
Рекурсивный:
Чтобы пройти по связанному списку, мы также можем использовать рекурсию. И подход аналогичен итеративному решению, нам нужно инициировать предыдущий узел как нулевой. Чтобы реализовать запуск предыдущей переменной в рекурсии, мы можем передать ее в качестве другого аргумента функции. Какой будет базовый вариант? Как и в приведенном выше решении, когда заголовок равен нулю, мы можем вернуть обратный связанный список.
Временная сложность вышеупомянутого решения - O (n), а пространственная сложность - O (n).
Надеюсь, это поможет вам по-разному взглянуть на решение аналогичной проблемы.
Ресурсы:
