Reverse Nodes in k-Group

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

Он выполняется за время O(L) для списка из L узлов: каждый узел учитывается один раз и переворачивается один раз. Версия с изменением на месте использует O(1) дополнительной памяти; копирование значений в массив использует O(L).

Q: Что происходит с последней группой, если в ней меньше k узлов?

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

СложноСвязный список

+10

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

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

Функция

reverseKGroup(next: integer-array, values: integer-array, k: integer) → integer-array

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

Ограничения

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

Примеры

Ввод: next = [2, 3, 4, -1, 1]values = [1, 4, 2, 5, 3]k = 2
Вывод: [2, 1, 4, 3, 5]
Пояснение: Список читается как 1, 2, 3, 4, 5 (узлы 0, 2, 4, 1, 3). Пары 1, 2 и 3, 4 расположены в обратном порядке, а 5 в одиночку короче, чем k = 2, поэтому он остается в конце.

Ввод: next = [5, 3, 6, -1, 7, 2, 4, 1]values = [10, 70, 30, 80, 50, 20, 40, 60]k = 3
Вывод: [30, 20, 10, 60, 50, 40, 70, 80]
Пояснение: Список читается как 10, 20, ..., 80. Группы 10, 20, 30 и 40, 50, 60 переставлены в обратном порядке. 70, 80 короче, чем k = 3, поэтому сохраняет свой порядок.

Ввод: next = [2, -1, 1]values = [7, 9, 3]k = 3
Вывод: [9, 3, 7]
Пояснение: Массив считывается как 7, 9, 3, а список — как 7, 3, 9. При k, равном длине, весь список составляет одну группу и выводится в обратном порядке: 9, 3, 7.

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

Можешь написать это рекурсивно, переворачивая одну группу и рекурсивно обрабатывая оставшуюся часть списка? Сколько дополнительной памяти для этого потребуется?

Подсказки

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

Открыто 0 из 3

Решение

Разворот всего списка — это один проход с переворотом ссылок. Здесь переворот выполняется каждые k узлов, и каждую перевёрнутую группу нужно соединить с частью перед ней и узлами после неё. Можно скопировать значения в массив и развернуть блоки или перенаправить ссылки каждой группы на месте, используя O(1) дополнительной памяти.

Скопируйте значения и разверните каждый блок в обратном порядке

Идея

Пройдите от узла 0 с помощью node = next[node] и скопируйте значения в массив в порядке следования в списке. Теперь группы — это блоки индексов 0–k-1, k–2k-1 и так далее: переверните каждый блок, который помещается целиком, а последний, более короткий блок оставьте без изменений. Это занимает время O(L) и дополнительную память O(L) и никогда не затрагивает ссылки.

Алгоритм

Идите от узла 0 до -1 и добавляйте values[node] в массив.
Для start = 0, k, 2k, ... при условии, что start + k ≤ L: разверните блок от индекса start до start+k-1.
Оставьте более короткий блок в конце без изменений.
Верните массив.

def reverseKGroup(next, values, k):
    # Read the values in list order.
    order = []
    node = 0
    while node != -1:
        order.append(values[node])
        node = next[node]
    # Reverse every full block of k; a shorter last block stays as it is.
    for start in range(0, len(order) - k + 1, k):
        order[start:start + k] = order[start:start + k][::-1]
    return order

Разверните каждую группу на месте, перенастроив связи

Идея

Чтобы развернуть весь список, пройдите по нему, используя prev и node, и задайте next[node] = prev. Для группы выполните тот же цикл k раз, начав с prev, равного after — узлу сразу после группы. Первый узел группы становится последним и указывает на after, поэтому оставшаяся часть списка остаётся присоединённой.

Перед разворотом посчитайте k узлов: если сначала встретится -1, значит, оставшаяся часть — короткая группа, и она остаётся без изменений. После разворота prev указывает на новый первый узел группы. Свяжите с ним последний узел предыдущей группы или сделайте его головой списка, если это первая группа. Прежний первый узел группы теперь является последним узлом обработанной части.

Каждый узел посещается дважды: один раз для подсчёта и один раз для разворота. Время выполнения — O(L), а памяти требуется несколько целых чисел (O(L) в R, где при первом изменении вектора ссылок создаётся его копия).

Алгоритм

Начни с head = 0, prevTail = -1, groupStart = 0.
Пройди k шагов от groupStart до after; если сначала дойдёшь до -1, перейди к шагу 5.
Установив prev = after и node = groupStart, повтори k раз: сохрани next[node], установи next[node] = prev, продвинь обе переменные.
Если prevTail равен -1, установи head = prev; иначе установи next[prevTail] = prev. Установи prevTail = groupStart, groupStart = after; перейди к шагу 2.
Собери значения, начиная с head.

def reverseKGroup(next, values, k):
    head = 0           # the list's head; changes after the first group
    prev_tail = -1     # last node of the groups already reversed
    group_start = 0
    while True:
        # Find the node right after this group, or stop if fewer than k remain.
        after, count = group_start, 0
        while after != -1 and count < k:
            after = next[after]
            count += 1
        if count < k:
            break
        # Turn the group's k links around. Its first node ends up last
        # and links to the node after the group.
        prev, node = after, group_start
        for _ in range(k):
            following = next[node]
            next[node] = prev
            prev, node = node, following
        # prev is the group's new first node: hang it after the previous group.
        if prev_tail == -1:
            head = prev
        else:
            next[prev_tail] = prev
        prev_tail = group_start
        group_start = after
    # Walk the relinked list from its head.
    result = []
    node = head
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

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

Разворот короткой последней группы. Перед разворотом посчитай узлы k; развёрнутую связь нельзя восстановить без ещё одного прохода.
Начало разворота с prev = -1, как при полном развороте. Тогда короткий хвост отваливается: первый пример возвращает 2, 1, 4, 3.
Не связывать последний узел предыдущей группы с новым первым узлом. Он по-прежнему указывает на старый первый узел, поэтому k-1 узлов исчезают.
Чтение ответа из узла 0 или чтение values слева направо. После разворота группы из k ≥ 2 узел 0 уже не является головой, а порядок массива никогда не совпадал с порядком списка.
Использование индексации с 0 в Lua и R, где массивы начинаются с 1. Оставляй индексы узлов нумерованными с 0 и читай next[node + 1].

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

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

Он выполняется за время O(L) для списка из L узлов: каждый узел учитывается один раз и переворачивается один раз. Версия с изменением на месте использует O(1) дополнительной памяти; копирование значений в массив использует O(L).

Что происходит с последней группой, если в ней меньше k узлов?

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

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

В случае узловых объектов фиктивный узел перед головой списка даёт первой группе узел перед ней, поэтому одна строка связывает каждую группу с готовой частью. В случае массива ссылок переменная prevTail, которая остаётся равной -1 до завершения первой группы, выполняет ту же задачу.

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

Тест #1

Тест #2

Тест #3

Аргументы

next = [2, 3, 4, -1, 1]
values = [1, 4, 2, 5, 3]
k = 2

Ожидаемый вывод

[2, 1, 4, 3, 5]