Восстановление связанного списка за один проход: шаг за шагом
Связанные списки - очень частая тема собеседований по разработке программного обеспечения. Хотя они могут быть пугающими и требующими некоторого обучения, они быстро становятся вашей второй натурой, чем больше вы работаете с ними.
Среди наиболее распространенных вопросов, связанных со связным списком, - переворот односвязного списка. Давайте разберем этот вопрос шаг за шагом. В этой статье я рассмотрю «однопроходное» итеративное решение. Они будут показаны в JavaScript, но концепции остаются неизменными для разных языков.
Обзор
В односвязном списке, чтобы перевернуть его, нам нужно будет просто взять все указатели и перевернуть их в противоположном направлении.
Пример:
1 → 2 → 3 → 4 → 5
Теперь становится:
1 ← 2 ← 3 ← 4 ← 5
Это то же самое, что:
5 → 4 → 3 → 2→ 1
Вот и все!
Решение
Сначала нам нужно определить наши указатели, которые мы будем использовать при обходе связанного списка.
Наш «текущий» узел будет во главе списка. Это будет вам дано.
Когда мы просматриваем список, нам нужно будет отслеживать узел перед текущим узлом (чтобы мы могли изменить наш указатель на него во время разворота), который мы будем называть «prev». Перед головой ничего нет, поэтому пока мы просто установим для нее значение null.
Мы также захотим сохранить следующий узел, чтобы мы могли легко получить к нему доступ. В нашем обходе мы установим указатель «следующий». А пока установите для него значение null.
let current = head let prev = null let next = null
Теперь мы готовы к обходу. Мы будем использовать простой цикл while. Мы остановим этот цикл while, как только наш «текущий» указатель окажется в конце списка. Мы знаем, что достигли конца списка, когда «текущий» указатель пытается установить себя на несуществующий узел, также известный как «null».
let prev = null let current = head let next = null while (current !== null) { }
Следующее, что нам нужно сделать, это сохранить следующий узел в той «следующей» переменной, которую мы определили ранее, чтобы мы могли получить к нему доступ позже. Это позволяет нам продолжить переход к следующему узлу в списке, когда мы перейдем к следующему циклу цикла. Мы получаем доступ к следующему узлу в списке, выбирая свойство «следующий» на нашем «текущем» узле.
let prev = null let current = head let next = null while (current !== null) { next = current.next }
Теперь мы собираемся изменить указатель, чтобы смотреть на предыдущий узел вместо следующего. Мы делаем это, устанавливая current.next так, чтобы он указывал на узел «prev». Вот где происходит разворот!
let prev = null let current = head let next = null while (current !== null) { next = current.next current.next = prev }
Теперь, когда все готово, нам нужно продвинуть вперед указатели узлов «текущий» и «предыдущий», чтобы подготовиться к следующей итерации. Узел после "prev" является "текущим", поэтому мы можем просто установить prev в значение current.
let prev = null let current = head let next = null while (current !== null) { next = current.next current.next = prev prev = current }
Хорошо, что мы сохранили следующий узел раньше! Потому что мы не могли просто сделать простой «current = current.next» из-за того, что мы сделали обратное. Это просто укажет нам на предыдущий узел. Мы бы оказались в затруднительном положении! Хорошо, давайте установим текущий узел как наш сохраненный «следующий» узел.
let prev = null let current = head let next = null while (current !== null) { next = current.next current.next = prev prev = current current = next }
Потрясающие! Мы завершили цикл! Теперь просто верните «текущий», верно? Нет, помните, что «current» имеет значение null в конце цикла, поэтому нам нужно вернуть то, что было перед ним, то есть «prev».
let prev = null let current = head let next = null while (current !== null) { next = current.next current.next = prev prev = current current = next } return prev
Теперь мы закончили!