Восстановление связанного списка за один проход: шаг за шагом

Восстановление связанного списка за один проход: шаг за шагом

Связанные списки - очень частая тема собеседований по разработке программного обеспечения. Хотя они могут быть пугающими и требующими некоторого обучения, они быстро становятся вашей второй натурой, чем больше вы работаете с ними.

Среди наиболее распространенных вопросов, связанных со связным списком, - переворот односвязного списка. Давайте разберем этот вопрос шаг за шагом. В этой статье я рассмотрю «однопроходное» итеративное решение. Они будут показаны в 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

Теперь мы закончили!