Middle of the Linked List
Дан односвязный список, хранящийся в двух массивах одинаковой длины. Узел i содержит значение values[i] и ссылку на узел next[i], -1 обозначает конец списка, а голова списка — это узел 0. Узлы хранятся не в порядке следования в списке, поэтому переходите по ссылкам.
Верните значение среднего узла. Если в списке чётное число узлов, то средних узлов два; верните значение второго из них.
Функция
- valuesinteger-array
- значение, хранящееся в каждом узле
- nextinteger-array
- индекс узла, на который ссылается каждый узел, или -1 для последнего узла
- Возвращаетinteger
- значение среднего узла, второго среднего узла, если длина чётная
Ограничения
1 ≤ n ≤ 5000, гдеn— длинаvaluesиnext.-104 ≤ values[i] ≤ 104- Каждый
next[i]равен-1или индексу узла от0доn-1. - Начиная с узла
0, список посещает каждый узел ровно один раз, а затем достигает-1. Цикла нет.
Примеры
- Ввод
- values = [4, 9, 2, 7, 5]next = [3, -1, 1, 4, 2]
- Вывод
- 5
- Пояснение
- Переходя по ссылкам из узла
0, получаем узлы0, 3, 4, 2, 1, поэтому список выглядит так:4, 7, 5, 2, 9. Третий из пяти узлов — это узел4, значение которого равно5. Собственный средний элемент массива,values[2] = 2, — это другой узел.
- Ввод
- values = [10, 20, 30, 40, 50, 60]next = [1, 2, 3, 4, 5, -1]
- Вывод
- 40
- Пояснение
- Здесь узлы хранятся по порядку. У шести узлов есть два средних —
30и40, и выбирается второй.
- Ввод
- values = [8]next = [-1]
- Вывод
- 8
- Пояснение
- Список из одного узла сам является серединой.
+13 скрытых тестов при отправке
Дополнительный вопрос
Можешь ли ты за один проход вернуть узел, находящийся на расстоянии одной трети списка от его начала? С какой скоростью должны двигаться указатели и где ты остановишься?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Ты не знаешь длину списка, пока не дойдёшь до его конца. Что, если два указателя начнут с головы списка, и один из них будет двигаться в два раза быстрее другого?
Когда быстрый указатель достигает конца, медленный проходит половину расстояния, поэтому останавливается на среднем узле. Осталось решить только, когда остановиться, чтобы при чётной длине указатель оказался на втором среднем узле.
Начните с
slowиfastв узле0. Покаfastне равен-1иnext[fast]не равно-1, перемещайте slow на одну ссылку, а fast — на две. Затем вернитеvalues[slow].
Решение
В массиве середина находится по индексу n / 2. У связного списка нет индексов: узнать его длину можно, только дойдя до конца, а к тому времени середина уже будет пройдена. Можно скопировать список в массив или сначала посчитать его элементы, а затем пройти по нему ещё раз. Элегантное решение — пустить по списку два указателя с разной скоростью, так что медленный окажется посередине, когда быстрый дойдёт до конца.
Скопируйте значения в массив
Идея
В этой задаче указатель — это индекс узла. Переход к следующему узлу выполняется так: node = next[node], а достижение -1 означает, что вы вышли за конец. В первом примере переходы от узла 0 идут так: 0 → 3 → 4 → 2 → 1 → -1.
Проблема списка в том, что нельзя сразу перейти к нужной позиции. Поэтому преобразуйте его в структуру, в которой это возможно: один раз пройдите по списку и по мере продвижения добавляйте каждое значение в новый массив. Этот массив хранит значения в порядке списка: в первом примере это [4, 7, 5, 2, 9], а его середина находится по индексу length / 2 с целочисленным делением.
Для списка чётной длины этот индекс сам по себе указывает на второй средний элемент: для шести значений индекс 3 — это четвёртое значение, то есть 40 во втором примере. Проход занимает время O(n), а копирование требует O(n) дополнительной памяти, которой позволяют избежать два следующих подхода.
Алгоритм
- Начни с пустого массива и
node = 0. - Пока
nodeне равен-1, добавляйvalues[node]и переходи кnext[node]. - Верни элемент с индексом
length / 2, округлённым вниз.
def middleNode(values, next):
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
return in_order[len(in_order) // 2]Считай, а затем пройди половину пути
Идея
Вам не нужна вся копия списка, нужна только его длина. Пройдите по списку один раз и посчитайте узлы. Затем вернитесь к началу и сделайте length / 2 шагов, округлив результат вниз. Узел, на котором вы остановитесь, и будет средним.
Почему нужно сделать именно столько шагов: после k шагов вы окажетесь на узле в позиции k, считая начало позицией 0. Средний элемент списка длины 5 находится в позиции 2, а второй средний элемент списка длины 6 — в позиции 3; оба значения получаются как length / 2. В первом примере вы считаете до 5, делаете два шага 0 → 3 → 4 и считываете values[4] = 5.
Теперь затраты памяти составляют O(1). Цена за это — повторный проход по половине списка: всего 1.5n перемещений, что по-прежнему соответствует O(n).
Алгоритм
- Перейди от узла
0к-1и посчитай узлы. - Вернись к узлу
0. - Выполни
node = next[node]ровноcount / 2раз, округлив результат вниз. - Верни
values[node].
def middleNode(values, next):
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
node = 0
for _ in range(length // 2):
node = next[node]
return values[node]Быстрый и медленный указатели
Идея
Поставь два указателя на начало списка. В каждом раунде slow перемещается на один узел, а fast — на два. После k раундов slow находится на позиции k, а fast — на позиции 2k, поэтому slow всегда проходит половину расстояния, пройденного fast. Когда fast достигает конца, slow оказывается в середине, и длина списка тебе ни разу не понадобилась.
Правило остановки определяет, какой из двух средних элементов ты получишь. Продолжай, пока fast указывает на существующий узел и после него есть ещё один узел: fast != -1 и next[fast] != -1. При нечётной длине fast останавливается на последнем узле. При чётной длине fast сходит с конца списка и становится равен -1, из-за чего slow перемещается ещё на один узел — ко второму среднему элементу. Во втором примере slow проходит 0, 1, 2, 3, а fast — 0, 2, 4, -1; values[3] равно 40.
В первом примере slow посещает узлы 0, 3, 4, а fast — 0, 4, 1; узел 1 — последний, поэтому цикл останавливается, когда slow находится на узле 4, и ответ равен 5. fast делает примерно n перемещений, а slow — n / 2, за один проход и с использованием двух целых чисел памяти.
Алгоритм
- Установи
slow = 0иfast = 0. - Пока
fast != -1иnext[fast] != -1, установиslow = next[slow]иfast = next[next[fast]]. - Верни
values[slow].
def middleNode(values, next):
slow = fast = 0
# Stop when fast is on the last node or has stepped past it.
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
return values[slow]
Ловушки и крайние случаи
Цикл короткий, поэтому ошибки связаны с тем, где он начинается, где останавливается и что возвращает.
- Возвращать
values[n / 2]. Узлы хранятся не в порядке списка, поэтому средний элемент массива обычно соответствует какому-то другому узлу. В первом примере возвращается2вместо5. - Получать первый из двух средних элементов при чётной длине. Цикл, который выполняется, пока
next[fast]иnext[next[fast]]оба являются действительными узлами, останавливается на один шаг раньше и во втором примере возвращает30вместо40. - Проверять
next[fast]доfast != -1. При чётной длине значение fast становится равным-1, и обращение кnext[-1]приводит к сбою в большинстве языков. В Python вместо этого без предупреждения считывается последний элемент, что ещё хуже. - В подходе с подсчётом проходить
count / 2 - 1шагов или округлять вверх. Считайте голову позицией0и делайте ровноcount / 2шагов, округляя вниз. - Возвращать индекс узла вместо его значения.
- Забывать о смещении в Lua и R, где нумерация массивов начинается с 1. Оставляйте индексы узлов с отсчётом от 0 и обращайтесь к
next[node + 1]. В Ruby и R словоnextзарезервировано, поэтому в начальных шаблонах параметр называетсяnext_.
Частые вопросы4
Почему быстрый и медленный указатели находят середину связного списка?
Оба начинают с головы списка, и на каждом шаге быстрый указатель перемещается на два узла, а медленный — на один. После k шагов быстрый указатель находится на позиции 2k, а медленный — на позиции k, то есть проходит ровно вдвое меньшее расстояние. Поэтому, когда быстрый указатель достигает конца списка, медленный находится в его середине.
Какова временная и пространственная сложность поиска середины связанного списка?
Все три подхода требуют времени O(n), поскольку найти середину невозможно, не пройдя примерно половину списка или больше. Копирование значений использует дополнительную память объёмом O(n). Подсчёт элементов и быстрый и медленный указатели требуют памяти объёмом O(1), причём указателям достаточно одного прохода.
Как вернуть первый средний узел вместо второго?
Измените условие остановки так, чтобы быстрый указатель останавливался на один шаг раньше: выполняйте цикл, пока next[fast] != -1 и next[next[fast]] != -1. Для шести узлов медленный указатель остановится на позиции 2, а не 3. При подсчёте пройдите (count - 1) / 2 шагов вместо count / 2.
Где ещё используется техника быстрого и медленного указателей?
Те же два указателя с разной скоростью позволяют обнаружить цикл в связном списке: в цикле быстрый указатель обгоняет медленный, и они встречаются. Они также помогают найти начало цикла и разделить список пополам для сортировки слиянием или проверки того, одинаково ли читается список в обоих направлениях.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
Python
def middleNode(values, next):
# Напишите код здесьСлучай 1
Случай 2
Случай 3
Ввод
values = [4, 9, 2, 7, 5] next = [3, -1, 1, 4, 2]
Ожидается
5