Palindrome Linked List

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

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

Q: Как быстрый и медленный указатели находят середину связного списка?

Оба начинают с головы списка, и быстрый указатель делает два шага на каждый шаг медленного. Когда быстрый указатель достигает конца, он проходит весь список, а медленный — половину.

Q: Разрушает ли обращение половины списка входные данные?

Да, это меняет связи во второй половине, и в большинстве языков этот массив принадлежит самому вызывающему коду. Если список всё ещё нужен, завершите сравнение, не возвращаясь раньше времени, а затем снова разверните эту половину. Средний узел по-прежнему связан с первым узлом этой половины, поэтому список снова целиком восстановлен с использованием дополнительной памяти O(1) .

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

+10

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

Верните true, если значения, прочитанные от головы до конца, совпадают со значениями, прочитанными от конца к голове, и false в противном случае.

Функция

isPalindrome(next: integer-array, values: integer-array) → boolean

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

Ограничения

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

Примеры

Ввод: next = [4, 3, -1, 2, 1]values = [3, 4, 3, 1, 1]
Вывод: true
Пояснение: Связи посещают узлы 0, 4, 1, 3, 2, поэтому список выглядит так: 3, 1, 4, 1, 3. Две тройки совпадают, две единицы совпадают, а у 4 посередине нет пары для сравнения.

Ввод: next = [2, -1, 3, 1]values = [4, 4, 9, 9]
Вывод: true
Пояснение: Список посещает узлы 0, 2, 3, 1 и считывает 4, 9, 9, 4 — одинаково в обоих направлениях.

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

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

Сможешь сделать это за время O(L) и используя O(1) дополнительной памяти?

Подсказки

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

Открыто 0 из 3

Решение

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

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

Идея

Здесь указатель — это индекс узла, а переход вперёд выполняется так: node = next[node]. Один раз пройдите по списку и скопируйте каждое значение в массив, который можно читать с обоих концов. Сравнивайте первое и последнее значения, перемещайте оба индекса к середине и возвращайте false при любом несовпадении. При нечётной длине среднее значение является парой самому себе.

Нужно прочитать каждое значение, поэтому время O(L) — наилучшее из возможных. Цена — L дополнительных целых чисел.

Алгоритм

Иди от узла 0 до -1 и добавляй каждый values[node] в массив.
Задай i = 0, а j — последний индекс.
Пока i < j, возвращай false, если значения различаются, иначе увеличивай i и уменьшай j.
Верни true.

def isPalindrome(next, values):
    # Write the values out in list order.
    seq = []
    node = 0
    while node != -1:
        seq.append(values[node])
        node = next[node]
    # Compare from both ends toward the middle.
    i = 0
    j = len(seq) - 1
    while i < j:
        if seq[i] != seq[j]:
            return False
        i += 1
        j -= 1
    return True

Разверните вторую половину на месте

Идея

Разверни ссылки второй половины вместо её копирования: проход от старого последнего узла теперь ведёт к середине. Чтобы найти середину, перемещай fast на два узла за каждый узел, на который перемещается slow, пока впереди у fast есть два узла. slow остановится на последнем узле первой половины, а если L нечётно — на среднем узле. В первом примере slow проходит 0 → 4 → 1, а fast — 0 → 1 → 2, поэтому slow останавливается на узле 4.

Разверни узлы после slow, затем одновременно проходи по left от начала списка и по right от развёрнутой половины: сначала 3 с 3, затем 1 с 1. Развёрнутая половина никогда не длиннее первой, поэтому, остановившись, когда закончится right, ты сравнишь именно нужные пары. Каждый этап проходит не более L узлов и хранит несколько целых чисел. В R изменение next_ копирует вектор один раз, поэтому R использует O(L) памяти.

Алгоритм

Установите slow = fast = 0. Пока и next[fast], и next[next[fast]] не равны -1, перемещайте slow на один узел, а fast — на два.
Разверните список, начинающийся с next[slow]: для каждого узла сохраните его ссылку, направьте её на prev, затем переместите prev и узел вперёд.
Установите left = 0 и right = prev, то есть голову развёрнутой половины.
Пока right != -1, при несовпадении верните false, иначе переместите оба указателя на один узел.
Верните true.

def isPalindrome(next, values):
    # Find the middle: fast moves two links for every one link slow moves.
    slow = 0
    fast = 0
    while next[fast] != -1 and next[next[fast]] != -1:
        slow = next[slow]
        fast = next[next[fast]]
    # slow is the last node of the first half (the middle node when the length is odd).
    # Reverse the links of the second half.
    prev = -1
    node = next[slow]
    while node != -1:
        after = next[node]
        next[node] = prev
        prev = node
        node = after
    # prev is the old last node, now the head of the reversed half.
    left = 0
    right = prev
    while right != -1:
        if values[left] != values[right]:
            return False
        left = next[left]
        right = next[right]
    return True

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

Проверка массивов вместо списка. В третьем примере values — это [1, 2, 1], но список имеет вид 1, 1, 2.
Проверка только next[fast] != -1. Затем fast может перейти к -1 и прочитать next[-1], что в большинстве языков выходит за допустимый диапазон, а в Python и Ruby без предупреждения означает последний элемент.
Сравнение до конца left вместо right. Средний узел по-прежнему связан со старой второй половиной, поэтому проход от головы списка получается длиннее.
Перезапись next[node] во время разворота до сохранения его значения, из-за чего остальная часть списка теряется.
В Lua и R, где нумерация массивов начинается с 1, чтение next[node] для идентификатора узла с нумерацией от 0. Читайте next[node + 1].

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

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

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

Как быстрый и медленный указатели находят середину связного списка?

Оба начинают с головы списка, и быстрый указатель делает два шага на каждый шаг медленного. Когда быстрый указатель достигает конца, он проходит весь список, а медленный — половину.

Разрушает ли обращение половины списка входные данные?

Да, это меняет связи во второй половине, и в большинстве языков этот массив принадлежит самому вызывающему коду. Если список всё ещё нужен, завершите сравнение, не возвращаясь раньше времени, а затем снова разверните эту половину. Средний узел по-прежнему связан с первым узлом этой половины, поэтому список снова целиком восстановлен с использованием дополнительной памяти O(1).

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

Тест #1

Тест #2

Тест #3

Аргументы

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

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

true