Remove Nth Node From End of List

Q: Как удалить n-й узел с конца связанного списка за один проход?

Используй два указателя с промежутком в n . Перемести первый на n узлов вперёд, затем перемещай оба указателя вместе, пока первый не окажется на последнем узле. Теперь второй стоит прямо перед узлом, который нужно удалить, поэтому укажи его ссылку на узел после удаляемого. Если первый указатель выйдет за пределы списка во время начального продвижения, удаляемый узел — голова списка.

Q: Какова временная и пространственная сложность удаления n-го узла с конца?

Для списка из L узлов требуется время O(L) , поскольку нужно дойти до конца, чтобы узнать, где находится целевой узел. Предварительный подсчёт и метод двух указателей используют дополнительную память объёмом O(1) . Копирование значений в массив требует O(L) .

Q: Решение с двумя указателями работает быстрее, чем предварительный подсчёт длины?

Ненамного: оба алгоритма имеют сложность O(L) , и два указателя вместе всё равно делают примерно столько же перемещений, сколько два прохода. Настоящее преимущество в том, что длину не нужно знать заранее, поэтому этот метод работает и тогда, когда список поступает как поток, который можно прочитать только один раз. Именно такой однократный проход обычно и требуют на собеседованиях.

СреднеСвязный список Два указателя

+10

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

Удалите n-й узел, считая с конца списка, где последний узел — 1-й с конца. Верните значения оставшихся узлов в порядке списка.

Функция

removeNthFromEnd(values: integer-array, next: integer-array, n: integer) → integer-array

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

Ограничения

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

Примеры

Ввод: values = [5, 9, 2, 7, 6]next = [2, 3, 4, -1, 1]n = 2
Вывод: [5, 2, 6, 7]
Пояснение: Переходя по ссылкам, начиная с узла 0, мы посещаем узлы 0, 2, 4, 1, 3, поэтому список имеет вид 5, 2, 6, 9, 7. Второй с конца — узел 1 со значением 9, и без него список имеет вид 5, 2, 6, 7. Элемент массива values[5-2] = 7 — последний узел, а не тот, который нужно удалить.

Ввод: values = [10, 20, 30, 40]next = [1, 2, 3, -1]n = 4
Вывод: [20, 30, 40]
Пояснение: Четыре узла и n = 4: узел, который находится четвёртым с конца, — это голова. Теперь список начинается с узла 1 и содержит 20, 30, 40.

Ввод: values = [42]next = [-1]n = 1
Вывод: []
Пояснение: Единственный узел является и головным, и последним узлом. Его удаление оставляет пустой список, поэтому ответ — [].

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

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

Можешь найти узел и отвязать его за один проход, не подсчитывая предварительно длину?

Подсказки

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

Открыто 0 из 3

Решение

Цель определяется расстоянием от конца, но в односвязном списке можно двигаться только вперёд, и вы узнаете, где находится конец, только когда дойдёте до него. Чтобы удалить узел, нужно также встать на узел перед ним, поскольку именно ссылка этого узла изменится. Можно скопировать список в массив или подсчитать его длину и пройти по нему ещё раз. Классическое решение состоит в том, чтобы держать два указателя на расстоянии n ссылок друг от друга, так что, когда передний указатель достигнет последнего узла, задний будет стоять непосредственно перед целевым узлом. Ниже L — количество узлов.

Скопируйте значения в массив

Идея

В этой задаче указатель — это индекс узла. Переход вперёд выполняется так: node = next[node], а достижение -1 означает, что вы вышли за конец. В первом примере обход от узла 0 проходит по пути 0 → 2 → 4 → 1 → 3 → -1.

Считать с конца сложно только потому, что у списка нет позиций. Поэтому задайте ему позиции: пройдите по списку один раз и добавьте каждое значение в массив. Для первого примера этот массив — [5, 2, 6, 9, 7]. В массиве из L значений последнее находится по индексу L-1, поэтому n-е значение с конца находится по индексу L-n. Здесь это 5-2 = 3, то есть 9. Удалите его и верните [5, 2, 6, 7].

Это правильное решение, которое работает за O(L) времени, но оно копирует весь список и не меняет ни одной ссылки. Суть задачи — изменить сам список, используя дополнительную память O(1). Именно это делают следующие два подхода.

Алгоритм

Начни с пустого массива и node = 0.
Пока node не равен -1, добавляй values[node] и переходи к next[node].
Удали элемент с индексом length - n.
Верни массив.

def removeNthFromEnd(values, next, n):
    # Write the values out in list order.
    order = []
    node = 0
    while node != -1:
        order.append(values[node])
        node = next[node]
    # Counting from the end, the n-th value sits at index len(order) - n.
    del order[len(order) - n]
    return order

Посчитайте узлы, затем отсоедините

Идея

Чтобы удалить узел из списка, измените ссылку узла перед ним так, чтобы она пропускала его: next[prev] = next[next[prev]]. Удалённый узел всё ещё находится в массивах, но ни один проход от головы больше до него не доберётся.

Итак, найдите prev. Подсчитайте узлы в первом проходе. Если считать голову позицией 0, целевой узел находится на позиции L-n, а узел перед ним — на позиции L-n-1; до него нужно пройти от головы L-n-1 шагов. В первом примере L = 5 и n = 2: два шага 0 → 2 → 4 приводят к узлу 4, который связан с узлом 1 — числом 9. Присваивание next[4] = next[1] = 3 даёт список 5, 2, 6, 7.

В одном случае перед целевым узлом нет другого узла: n = L, когда целевой узел — голова. Тогда ничего перенастраивать не нужно. Список начинается с next[0], а не с 0, как во втором примере. Затем пройдите от головы, чтобы собрать ответ. Два прохода по списку требуют примерно 2L перемещений, а дополнительная память помимо ответа составляет всего несколько целых чисел.

Алгоритм

Пройдите от узла 0 до -1 и посчитайте узлы, получив L.
Если n == L, новая голова — это next[0].
В противном случае начните с узла 0, задав его как prev, и переместите его L-n-1 раз, затем задайте next[prev] = next[next[prev]].
Пройдите от головы и соберите values[node] по порядку.

def removeNthFromEnd(values, next, n):
    # First pass: count the nodes.
    length = 0
    node = 0
    while node != -1:
        length += 1
        node = next[node]
    head = 0
    if n == length:
        # The node to remove is the head, so the list starts at its second node.
        head = next[0]
    else:
        # Second pass: stop on the node just before position length - n.
        prev = 0
        for _ in range(length - n - 1):
            prev = next[prev]
        next[prev] = next[next[prev]]  # skip over the removed node
    result = []
    node = head
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Два указателя на расстоянии n ссылок

Идея

Можно определить элемент на позиции «n с конца», не зная L. Продвинь fast на n звеньев вперёд, пока slow ждёт у головы списка. Затем перемещай оба указателя по одному звену за раз. Расстояние между ними остаётся равным n, поэтому, когда fast окажется на последнем узле (next[fast] == -1, позиция L-1), slow будет на позиции L-1-n: на узле прямо перед целевым. Одна операция next[slow] = next[next[slow]] удаляет целевой узел из списка.

Рассмотрим первый пример. fast делает два шага: 0 → 2 → 4. Теперь перемещаются оба указателя: slow переходит на 2, а fast — на 1, затем slow переходит на 4, а fast — на 3. Узел 3 — последний, поэтому останавливаемся. next[4] — это узел 1, то есть 9, а присваивание next[4] = next[1] = 3 удаляет его.

Случай с головой списка обрабатывается сам собой. Поскольку n ≤ L, fast достигает -1 во время начального продвижения только при n = L, и именно тогда целевым является головной узел. При работе с объектами узлов можно добавить фиктивный узел перед головой, чтобы этот случай не возникал; здесь ту же задачу решает проверка fast == -1. Поиск и удаление узла требуют одного прохода. Запись результата требует ещё одного прохода, который нужен при любом подходе.

Алгоритм

Установите fast = 0 и переместите его n раз с помощью fast = next[fast].
Если fast == -1, целевым является начало списка: новое начало — next[0].
Иначе установите slow = 0 и перемещайте оба указателя, пока next[fast] != -1.
Установите next[slow] = next[next[slow]].
Пройдите от начала списка и соберите значения values[node] по порядку.

def removeNthFromEnd(values, next, n):
    # Send fast n links ahead of slow.
    fast = 0
    for _ in range(n):
        fast = next[fast]
    head = 0
    if fast == -1:
        # Fast fell off the end, so the list has exactly n nodes: remove the head.
        head = next[0]
    else:
        # Move both, keeping the gap. When fast stands on the last node,
        # slow stands just before the node to remove.
        slow = 0
        while next[fast] != -1:
            slow = next[slow]
            fast = next[fast]
        next[slow] = next[next[slow]]  # skip over the removed node
    result = []
    node = head
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

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

Большинство неправильных ответов связано с тем, где останавливается указатель follower, а также со случаем удаления головы списка.

Удаление элемента по индексу массива L-n. Узлы хранятся не в порядке списка, поэтому по этому индексу обычно находится какой-то другой узел. В первом примере values[3] = 7 — это последний узел, а не 9.
Остановка при fast == -1 вместо остановки при next[fast] == -1. Это перемещает slow на один шаг дальше, прямо на целевой узел, а в односвязном списке нельзя отсоединить узел от него самого.
Забыть про случай с головой списка. Когда n = L, после начального перемещения головы fast равен -1, и чтение next[fast] приводит к сбою в большинстве языков. Python читает next[-1] без ошибок и возвращает неправильный список, что сложнее заметить.
Отсоединение с помощью next[slow] = next[slow] + 1 или slow + 2. Соседние узлы списка не являются соседними элементами массивов; единственный способ перейти к узлу после целевого — это next[next[slow]].
Сбор ответа, начиная с узла 0, после удаления головы списка. Начни финальный проход с новой головы.
Забыть о смещении в Lua и R, где индексация массивов начинается с 1. Сохраняй индексы узлов нулевыми и читай next[node + 1]. В Ruby и R слово next зарезервировано, поэтому в решениях для начинающих параметр называется next_.

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

Как удалить n-й узел с конца связанного списка за один проход?

Используй два указателя с промежутком в n. Перемести первый на n узлов вперёд, затем перемещай оба указателя вместе, пока первый не окажется на последнем узле. Теперь второй стоит прямо перед узлом, который нужно удалить, поэтому укажи его ссылку на узел после удаляемого. Если первый указатель выйдет за пределы списка во время начального продвижения, удаляемый узел — голова списка.

Почему в решениях этой задачи используют фиктивный узел?

Удаление узла означает изменение ссылки в предыдущем узле, а у головы списка нет предыдущего узла. Фиктивный узел, помещённый перед головой списка, даёт каждому узлу, включая голову, предшественника, поэтому одна строка отвязки охватывает все случаи. Тогда ответ начинается со следующего узла после фиктивного. Проверка того, не вышел ли ведущий указатель за пределы списка после n шагов, обрабатывает тот же случай без дополнительного узла.

Какова временная и пространственная сложность удаления n-го узла с конца?

Для списка из L узлов требуется время O(L), поскольку нужно дойти до конца, чтобы узнать, где находится целевой узел. Предварительный подсчёт и метод двух указателей используют дополнительную память объёмом O(1). Копирование значений в массив требует O(L).

Решение с двумя указателями работает быстрее, чем предварительный подсчёт длины?

Ненамного: оба алгоритма имеют сложность O(L), и два указателя вместе всё равно делают примерно столько же перемещений, сколько два прохода. Настоящее преимущество в том, что длину не нужно знать заранее, поэтому этот метод работает и тогда, когда список поступает как поток, который можно прочитать только один раз. Именно такой однократный проход обычно и требуют на собеседованиях.

Python

def removeNthFromEnd(values, next, n):
    # Напишите код здесь

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

Случай 1

Случай 2

Случай 3

Ввод

values = [5, 9, 2, 7, 6]
next = [2, 3, 4, -1, 1]
n = 2

Ожидается

[5, 2, 6, 7]

Remove Nth Node From End of List

Функция

Ограничения

Примеры

Подсказки

Решение

Скопируйте значения в массив

Посчитайте узлы, затем отсоедините

Два указателя на расстоянии n ссылок

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

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

Похожие задачи