Reorder List

Q: Зачем переворачивать вторую половину списка?

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

Q: Какова временная сложность Reorder List?

Метод на месте работает за время O(n) и использует O(1) дополнительной памяти: поиск середины, разворот и переплетение требуют посетить каждый узел постоянное число раз. Копирование значений в массив также занимает время O(n) , но требует O(n) памяти, а перемещение хвоста вперёд по одному узлу занимает O(n²) .

Q: Где находится середина, если список содержит чётное количество узлов?

Останови медленный указатель на последнем узле передней половины. При шести узлах половины состоят из трёх и трёх узлов; при пяти — из трёх и двух. Тогда дополнительный узел завершает ответ: именно там порядок помещает среднее значение.

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

+10

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

Обозначим узлы в порядке следования в списке как L0, L1, ..., Lk. Переставьте узлы так, чтобы список имел порядок L0, Lk, L1, Lk-1, L2, Lk-2, ...: сначала первый узел, затем последний, потом второй, затем предпоследний и так далее. Верните значения в новом порядке.

Функция

reorderList(next: integer-array, values: integer-array) → integer-array

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

Ограничения

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

Примеры

Ввод: next = [3, 4, -1, 1, 2]values = [1, 3, 5, 2, 4]
Вывод: [1, 5, 2, 4, 3]
Пояснение: Если следовать по ссылкам от узла 0, список будет таким: 1, 2, 3, 4, 5. Первый, последний, второй и предпоследний элементы дают 1, 5, 2, 4, а среднее значение 3 идёт последним.

Ввод: next = [2, 3, 1, -1]values = [10, 30, 20, 40]
Вывод: [10, 40, 20, 30]
Пояснение: Список посещает узлы 0, 2, 1, 3 и считывает значения 10, 20, 30, 40. Сначала первый и последний дают 10, 40, затем внутренняя пара даёт 20, 30.

Ввод: next = [-1]values = [7]
Вывод: [7]
Пояснение: В списке с одним узлом нечего перемещать, поэтому ответ — [7].

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

Сможете ли вы переставить сами ссылки, используя дополнительную память O(1)?

Подсказки

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

Открыто 0 из 3

Решение

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

Перемещайте хвост вперёд, по одному узлу за раз

Идея

Здесь указатель — это индекс узла, а переход вперёд выполняется с помощью node = next[node]. За первым узлом идёт последний, поэтому отсоедините последний узел и вставьте его после текущего, затем повторите, переместившись ещё на два узла вперёд. Для 1, 2, 3, 4, 5 получится 1, 5, 2, 3, 4, затем 1, 5, 2, 4, 3. Остановитесь, когда за текущим узлом останется меньше двух узлов.

Чтобы найти узел перед последним, каждый раз приходится проходить до конца. С каждым раундом путь сокращается на два узла, всего получается примерно n²/4 перемещений: четыре миллиона для 4000 узлов.

Алгоритм

Установи cur = 0.
Пока за cur следуют как минимум два узла, перемещай before от cur, пока next[next[before]] == -1, так что tail = next[before] — последний узел.
Отсоедини его с помощью next[before] = -1, затем вставь его: next[tail] = next[cur] и next[cur] = tail.
Перемести cur в next[tail] и повтори.
Пройди от узла 0 и собери значения.

def reorderList(next, values):
    cur = 0
    # While at least two nodes follow cur, move the last node right after cur.
    while next[cur] != -1 and next[next[cur]] != -1:
        before = cur
        while next[next[before]] != -1:  # find the node before the tail
            before = next[before]
        tail = next[before]
        next[before] = -1
        next[tail] = next[cur]
        next[cur] = tail
        cur = next[tail]
    result = []
    node = 0
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

Скопируйте значения и считывайте их с обоих концов

Идея

Массив достигает своего последнего элемента за один шаг. Скопируй значения в порядке списка: [1, 2, 3, 4, 5] в первом примере, затем читай с помощью lo с начала и hi с конца: возьми lo, возьми hi и сдвигай оба указателя к середине, пока lo < hi. Получится 1, 5, 2, 4; при нечётной длине оба указателя встретятся на среднем 3, который пойдёт последним.

Это занимает время O(n) и дополнительную память O(n), а ссылки никогда не меняются.

Алгоритм

Начните с узла 0 и добавляйте каждое значение в inOrder.
Установите lo = 0, а hi — в последний индекс.
Пока lo < hi, добавляйте inOrder[lo] и inOrder[hi], затем увеличивайте lo и уменьшайте hi.
Если lo == hi, добавьте среднее значение.

def reorderList(next, values):
    # Write the values out in list order.
    in_order = []
    node = 0
    while node != -1:
        in_order.append(values[node])
        node = next[node]
    # Take from the front and the back in turn.
    result = []
    lo, hi = 0, len(in_order) - 1
    while lo < hi:
        result.append(in_order[lo])
        result.append(in_order[hi])
        lo += 1
        hi -= 1
    if lo == hi:  # odd length: the middle value comes last
        result.append(in_order[lo])
    return result

Найди середину, переверни вторую половину и переплети

Идея

Для 1, 2, 3, 4, 5, 6 ответ — 1, 6, 2, 5, 3, 4: первая половина 1, 2, 3 идёт по порядку, чередуясь со второй половиной 4, 5, 6, прочитанной в обратном порядке. Поэтому разрежьте список посередине, разверните вторую половину и переплетите их.

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

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

Алгоритм

Перемещайте slow на один узел, а fast — на два узла, пока next[fast] и next[next[fast]] не равны -1.
Задайте second = next[slow], затем next[slow] = -1.
Разверните список, начинающийся с second; его новая голова — prev.
Чередуйте узлы: пока second не равен -1, свяжите first с second, а second — со старым next[first], затем продвиньте оба указателя.
Пройдите от узла 0 и соберите значения.

def reorderList(next, values):
    # 1. Find the middle: slow stops on the last node of the first half.
    slow = fast = 0
    while next[fast] != -1 and next[next[fast]] != -1:
        slow = next[slow]
        fast = next[next[fast]]
    second = next[slow]
    next[slow] = -1  # cut the list in two
    # 2. Reverse the second half.
    prev = -1
    while second != -1:
        after = next[second]
        next[second] = prev
        prev = second
        second = after
    # 3. Weave: one node from the front half, one from the reversed back half.
    first, second = 0, prev
    while second != -1:
        first_after, second_after = next[first], next[second]
        next[first] = second
        next[second] = first_after
        first, second = first_after, second_after
    result = []
    node = 0
    while node != -1:
        result.append(values[node])
        node = next[node]
    return result

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

Не обрезать список после середины. Без next[slow] = -1 первая половина всё ещё указывает на вторую, и после чередования список зацикливается.
Перезапись ссылки до её сохранения. При обращении списка и чередовании сначала считайте next[node] в переменную, иначе остаток списка будет потерян.
Чередование до конца первой половины. При нечётной длине этот цикл выполнится ещё раз, когда second равен -1, и прочитает next[-1].
Путать порядок элементов массива с порядком списка. В первом примере values равно [1, 3, 5, 2, 4], но список читается как 1, 2, 3, 4, 5.
В Lua и R массивы начинаются с 1. Оставляйте индексы узлов 0-индексированными и обращайтесь к next[node + 1].

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

Зачем переворачивать вторую половину списка?

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

Какова временная сложность Reorder List?

Метод на месте работает за время O(n) и использует O(1) дополнительной памяти: поиск середины, разворот и переплетение требуют посетить каждый узел постоянное число раз. Копирование значений в массив также занимает время O(n), но требует O(n) памяти, а перемещение хвоста вперёд по одному узлу занимает O(n²).

Где находится середина, если список содержит чётное количество узлов?

Останови медленный указатель на последнем узле передней половины. При шести узлах половины состоят из трёх и трёх узлов; при пяти — из трёх и двух. Тогда дополнительный узел завершает ответ: именно там порядок помещает среднее значение.

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

Тест #1

Тест #2

Тест #3

Аргументы

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

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

[1, 5, 2, 4, 3]

Reorder List

Функция

Ограничения

Примеры

Подсказки

Решение

Перемещайте хвост вперёд, по одному узлу за раз

Скопируйте значения и считывайте их с обоих концов

Найди середину, переверни вторую половину и переплети

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

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

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