Reverse Linked List

Q: Как развернуть связный список на месте?

Пройдите по списку с двумя указателями: prev , изначально равным ничему, и node , изначально указывающим на голову списка. На каждом узле сохраните ссылку на следующий узел, направьте его ссылку на prev , затем переместите prev и node на один шаг вперёд. Когда узлы node закончатся, prev будет головой развёрнутого списка.

Q: Каковы временная и пространственная сложности разворота связанного списка?

Итеративная версия посещает каждый узел один раз, время — O(n) , и использует три указателя, дополнительная память — O(1) . Сначала скопировать порядок в массив — тоже время O(n) , но потребуется дополнительная память O(n) . Рекурсивная версия использует O(n) памяти для стека вызовов.

ЛегкоСвязный список

+10

Дан односвязный список, хранящийся в массиве next: узел i ссылается на узел next[i], -1 обозначает конец списка, а голова — это узел 0. Узлы хранятся не в порядке списка, поэтому следуйте по ссылкам.

Разверните список, изменив направление каждой ссылки так, чтобы прежний последний узел стал головой, а узел 0 стал последним и ссылался на -1. Верните обновлённый массив next, длина которого совпадает с длиной входного массива.

Функция

reverseList(next: integer-array) → integer-array

nextinteger-array: индекс узла, на который ссылается каждый узел, или -1 для последнего узла
Возвращаетinteger-array: следующий массив перевёрнутого списка

Ограничения

1 ≤ next.length ≤ 5000
Каждый next[i] — это -1 или индекс узла от 0 до next.length-1.
Начиная с узла 0, список посещает каждый узел ровно один раз, а затем достигает -1. Цикла нет.

Примеры

Ввод: next = [1, 2, 3, -1]
Вывод: [-1, 0, 1, 2]
Пояснение: Список имеет вид 0 → 1 → 2 → 3. В обратном порядке это 3 → 2 → 1 → 0, поэтому узел 3 связан с 2, узел 2 — с 1, узел 1 — с 0, а узел 0 — с -1.

Ввод: next = [2, -1, 3, 1]
Вывод: [-1, 3, 0, 2]
Пояснение: Список выглядит так: 0 → 2 → 3 → 1, а в обратном порядке — так: 1 → 3 → 2 → 0. Если записать каждую новую ссылку по индексу её узла, получится [-1, 3, 0, 2]. Если обратить порядок самого массива, получится [1, 3, -1, 2], что не одно и то же.

Ввод: next = [-1]
Вывод: [-1]
Пояснение: Узел является своей собственной обратной копией. Он остаётся и головой, и хвостом, и по-прежнему указывает на -1.

+11 скрытых тестов при отправке

Дополнительный вопрос

Можешь развернуть только часть списка между позицией left и позицией right, оставив узлы до и после неё на своих местах?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

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

Запиши порядок, затем свяжи заново

Идея

В этой задаче указатель — это индекс узла, а переход вперёд выполняется с помощью node = next[node]. Идите от узла 0, пока не достигнете -1, и записывайте каждый узел, который проходите. Во втором примере получается порядок [0, 2, 3, 1].

В перевёрнутом списке каждый узел ссылается на узел, который шёл перед ним в этом порядке: 1 ссылается на 3, 3 — на 2, 2 — на 0. У первого узла в порядке, прежней головы списка, перед ним ничего нет, поэтому он ссылается на -1. Заполните новый массив этими ссылками и верните его.

Поскольку каждая ссылка записывается в новый массив, ничего не перезаписывается, пока оно ещё нужно, поэтому в этой версии сложно допустить ошибку. Она требует времени O(n) и дополнительной памяти O(n) для порядка и нового массива.

Алгоритм

Пройди от узла 0 до -1 и добавляй каждый узел в order.
Создай новый массив той же длины.
Установи для элемента order[0] значение -1.
Для каждого k ≥ 1 установи для элемента order[k] значение order[k-1].
Верни новый массив.

def reverseList(next):
    order = []
    node = 0
    while node != -1:
        order.append(node)
        node = next[node]
    reversed_next = [0] * len(next)
    reversed_next[order[0]] = -1  # the old head ends the new list
    for k in range(1, len(order)):
        reversed_next[order[k]] = order[k - 1]
    return reversed_next

Измените ссылки на противоположные за один проход

Идея

Ты можешь развернуть каждую ссылку, когда доходишь до соответствующего узла, если помнишь узел, из которого пришёл. Храни prev — узел позади тебя; начальное значение — -1, потому что прежняя голова станет последним узлом. В узле node ссылка next[node] указывает вперёд; присвой ей значение prev, чтобы она указывала назад.

Эта запись уничтожает единственный способ двигаться дальше, поэтому сначала сохрани его в третьей переменной: after = next[node]. Затем разверни ссылку и передвинь оба указателя на один шаг: prev = node, node = after. В любой момент узлы позади тебя образуют развернутый список с головой prev, а узлы впереди — нетронутую оставшуюся часть, начинающуюся с node. Когда node достигнет -1, все ссылки будут развернуты, а prev станет новой головой.

Во втором примере указатели перемещаются по узлам 0, 2, 3, 1, выполняя записи next[0] = -1, next[2] = 0, next[3] = 2 и next[1] = 3. Каждый узел посещается один раз: время — O(n), а единственная используемая память — три целых числа: O(1).

Алгоритм

Установи prev = -1 и node = 0.
Пока node не равно -1, сохрани after = next[node].
Установи next[node] = prev.
Перейди дальше: prev = node, затем node = after.
Верни next.

def reverseList(next):
    prev = -1  # the node behind the current one; the old head will point to -1
    node = 0
    while node != -1:
        after = next[node]  # save the rest of the list before cutting the link
        next[node] = prev
        prev = node
        node = after
    return next

Ловушки и крайние случаи

Почти каждая ошибка здесь связана с порядком трёх присваиваний или с двумя концами списка.

Перезапись next[node] до его сохранения. После next[node] = prev старая ссылка вперёд исчезает, и обход перемещается назад вместо перехода к следующему узлу.
Начальное значение prev отличается от -1. Старый начальный узел должен стать концом нового списка. Если начать с 0, узел 0 будет ссылаться сам на себя.
Разворот массива вместо ссылок. Узлы хранятся не в порядке списка, и в ответе каждый узел остаётся на своём индексе; меняются только значения. Разворот [2, -1, 3, 1] даёт [1, 3, -1, 2], а не [-1, 3, 0, 2].
Остановка на один узел раньше из-за цикла с условием next[node] != -1. Ссылку последнего узла тоже нужно развернуть, поэтому цикл должен выполняться, пока node != -1.
Разворот длинного списка с помощью рекурсии. Для списка из 5000 узлов нужны 5000 вложенных вызовов, что превышает ограничение Python в 1000.
Забытый сдвиг в Lua и R, где массивы начинаются с 1. Оставляй индексы узлов с нуля и обращайся к next[node + 1]. Ruby и R резервируют слово next, поэтому в их начальных решениях параметр называется next_.

Частые вопросы4

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

Пройдите по списку с двумя указателями: prev, изначально равным ничему, и node, изначально указывающим на голову списка. На каждом узле сохраните ссылку на следующий узел, направьте его ссылку на prev, затем переместите prev и node на один шаг вперёд. Когда узлы node закончатся, prev будет головой развёрнутого списка.

Каковы временная и пространственная сложности разворота связанного списка?

Итеративная версия посещает каждый узел один раз, время — O(n), и использует три указателя, дополнительная память — O(1). Сначала скопировать порядок в массив — тоже время O(n), но потребуется дополнительная память O(n). Рекурсивная версия использует O(n) памяти для стека вызовов.

Можешь ли ты рекурсивно развернуть связный список?

Да. Разверни всё после головного узла, затем заставь прежний следующий узел головного узла указывать обратно на него и установи ссылку головного узла в значение «ничего». Это читается хорошо, но для каждого узла выполняется один вложенный вызов, поэтому длинный список может переполнить стек вызовов. По умолчанию Python останавливается после 1000 вызовов, а список из 5000 узлов превышает это значение.

Почему для разворота связного списка нужны три указателя?

Чтобы развернуть ссылку узла, нужны сам узел и узел перед ним — это два указателя. В третьем хранится узел после него, потому что разворот ссылки стирает единственную ссылку на остальную часть списка. Без неё обход не сможет продолжиться.

Python

def reverseList(next):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

next = [1, 2, 3, -1]

Ожидается

[-1, 0, 1, 2]