Как изменить односвязный список в JavaScript итеративно и рекурсивно.

Распространенный вопрос на собеседовании, с которым вы можете столкнуться, если подаете заявку на должность инженера-программиста (особенно в крупных компаниях типа FAANG), - это перевернуть связанный список.

Если вы знакомы с тем, что такое связанные списки, эта проблема может показаться простой задачей. Ну не так быстро!

Обратное обращение связанного списка включает несколько различных шагов, которые необходимо выполнить в определенном порядке. Итак, давайте начнем с того, что рассмотрим, что на самом деле представляют собой связанные списки и какие типы связанных списков вы, скорее всего, встретите в реальной жизни.

Что такое связанные списки?

Связанный список - это структура данных. Это набор элементов или узлов, хранящихся линейно, причем каждый узел содержит указатель, который ссылается на следующий узел в списке, таким образом связывая весь набор узлов друг с другом. Это основной обзор концепции. Сейчас существует несколько типов связанных списков, таких как односвязные и двусвязные списки. Здесь мы просто реализуем первый.

Списки Односвязные представляют собой набор узлов, каждый из которых содержит следующий указатель, ссылающийся на следующий узел, до тех пор, пока следующий указатель последнего узла не будет указывать на нуль.

{1, next} => {2, next} => {3, next} => {4, next} => null

Двусвязные списки также представляют собой совокупность узлов, хотя они имеют указатель на следующий узел, как односвязные списки, они также содержат указатель на предыдущий узел.

{prev, 1, next} <=> {prev, 2, next} <=> {prev, 3, next} => null

Итерационный подход

Чтобы итеративно перевернуть односвязный список, мы должны настроить указатели узлов каждого узла так, чтобы они указывали на предыдущий узел в списке. Поскольку в односвязном списке есть только узлы со следующими указателями, нам нужно вручную отслеживать предыдущий узел перед каждым узлом, по которому мы в данный момент проходим.

Чтобы решить эту проблему, мы должны манипулировать указателями узлов на месте, а не создавать новый связанный список.

Ниже показано, как будут выглядеть узлы односвязного списка:

Теперь, когда у нас есть наглядное представление о том, с чем мы будем работать, давайте реализуем наше решение в функции reverse() ниже.

В строках 5-7 мы устанавливаем несколько указателей для отслеживания текущего узла, предыдущего узла перед текущим и следующего узла после текущего. Затем для строк 10–15 мы выполняем цикл для выполнения нашего разворота, регулируя указатели узлов во время каждой итерации, чтобы перевернуть связанный список на месте. Когда разворот завершен, мы выходим из цикла. В строках 17–18 мы сбрасываем заголовок так, чтобы он был последним узлом в исходном порядке односвязного списка, и возвращаем ссылку на новый заголовок.

Before: {1, next} => {2, next} => {3, next} => {4, next} => null
After:  {4, next} => {3, next} => {2, next} => {1, next} => null

Рекурсивный подход

Мы уже видели, как мы можем реверсировать список итеративно, теперь давайте рассмотрим, как рекурсивно реверсировать односвязный список.

Мы начнем сверху с головного узла, чтобы перевернуть список, а затем рекурсивно пройдемся вниз по стеку вызовов, пока не дойдем до последнего узла. Когда мы достигаем последнего узла, мы можем вернуться назад по стеку вызовов, меняя список, изменяя по ходу указатель следующего узла каждого узла. Как только мы вернемся наверх, так как мы сохранили ссылку на последний узел (новый заголовок), мы можем просто вернуть его, дав нам полностью перевернутый список.

Строка 3–5 - это наше условие выхода: когда мы закончим перевернуть связанный список, мы просто вернем сюда новый заголовок. Тогда строки 6–9 - это ядро ​​нашего алгоритма. Строка 6 - это место, где мы движемся вниз по стеку вызовов, пока не дойдем до конца списка. Строки 7 и 8 - это то место, где мы настраиваем наши следующие указатели, чтобы перевернуть ссылки, а строка 9 - это то место, где мы возвращаем стек вызовов с оцененным результатом reversedHead.

Изображение ниже может помочь понять эту логику. Он показывает, как выглядит стек вызовов для этой проблемы:

         -----------------CALL STACK-------------------
         -(head)(reversedHead)-------------------------
         ----------(head)(reversedHead)----------------
         -------------------(head)(reversedHead)-------
         ---------------------------------------(head)-

На изображении выше каждая строка представляет собой кадр стека, который создается для каждого рекурсивного вызова функции. Верхняя ссылка на голову - это когда она впервые передается в нашу recursivelyReverseList() функцию. Последняя строка представляет собой базовый случай, когда мы достигаем конца списка. Затем обращение происходит при возврате стека вызовов назад со ссылкой на новый заголовок списка.

Резюме

Изучение того, как перевернуть связанный список, может стать отличным упражнением для изучения типичных проблем собеседования. Это может вас сильно сбить с толку (как и меня!), Но если вы будете продолжать, вы сможете лучше понять эту фундаментальную структуру данных.

Ресурсы

Больше контента на plainenglish.io