Sort List
Дан односвязный список, хранящийся в двух массивах одинаковой длины. Узел i содержит значение values[i] и ссылку на узел next[i], -1 обозначает конец списка, а головой является узел 0. Узлы хранятся не в порядке списка, и в массивах также могут быть лишние узлы, до которых не доходит обход от узла 0. Они не являются частью списка, даже если их ссылки указывают на его узлы.
Отсортируйте список по неубыванию значений и верните значения его узлов в этом порядке.
Функция
- 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, не посещая один и тот же узел дважды. - Узлы, до которых не доходит обход, начинающийся с узла
0, не являются частью списка. Их записиnextмогут указывать куда угодно.
Примеры
- Ввод
- next = [3, -1, 4, 2, 1]values = [4, 1, 3, 2, 5]
- Вывод
- [1, 2, 3, 4, 5]
- Пояснение
- Обход от узла
0посещает узлы0, 3, 2, 4, 1, поэтому список выглядит так:4, 2, 3, 5, 1. В отсортированном виде это1, 2, 3, 4, 5.
- Ввод
- next = [2, 0, -1, -1]values = [6, 9, -2, 5]
- Вывод
- [-2, 6]
- Пояснение
- Список — это
0 → 2, что соответствует значениям6, -2. До узлов1и3нельзя добраться от головы списка, поэтому их значения9и5пропущены, несмотря на то что узел1связан с узлом0.
- Ввод
- next = [1, 2, 3, -1]values = [3, -1, 3, -1]
- Вывод
- [-1, -1, 3, 3]
- Пояснение
- В списке указаны значения
3, -1, 3, -1. Равные значения остаются в ответе столько раз, сколько они встречаются:-1, -1, 3, 3.
Дополнительный вопрос
Сможешь ли ты отсортировать, переподключив узлы, за время O(n log n), не копируя значения?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Каким алгоритмам сортировки нужно переходить в произвольную позицию, а какие всегда проходят по входным данным только вперёд? Связный список хорошо подходит для второго типа.
Для объединения двух отсортированных списков в один не требуется дополнительная память: нужно перепривязать узлы, каждый раз выбирая меньшее из двух первых значений. Если бы можно было разделить список на две отсортированные половины, одной операции слияния было бы достаточно.
Найди середину с помощью медленного и быстрого указателей и разрежь список там. Отсортируй каждую половину тем же способом, останавливаясь на одном узле, который уже отсортирован. Затем объедини две отсортированные половины и верни новую голову списка.
Решение
Быстрая сортировка и пирамидальная сортировка полагаются на произвольный доступ, а односвязный список перемещается только вперёд. Сортировка слиянием подходит: разделение списка посередине и слияние двух отсортированных списков выполняются проходом вперёд, поэтому она сортирует сами связи за O(n log n). Здесь n — длина массивов.
Скопируйте значения в массив и отсортируйте его
Идея
Список — это то, что посещает обход node = next[node], начиная с узла 0 и заканчивая -1. Соберите эти значения в новый массив, отсортируйте его встроенной функцией сортировки и верните его. Нельзя сортировать напрямую values: во втором примере в нём хранятся 9 и 5, которых нет в списке.
Обход занимает O(n), а сортировка — O(n log n); дополнительная память — O(n). Сам список никогда не изменяется, поэтому на собеседованиях спрашивают о следующем подходе.
Алгоритм
- Начни с пустого массива и
node = 0. - Пока
nodeне равен-1, добавляйvalues[node]и переходи кnext[node]. - Отсортируй массив по возрастанию и верни его.
def sortList(next, values):
# Collect the values of the nodes on the list, then sort them.
on_list = []
node = 0
while node != -1:
on_list.append(values[node])
node = next[node]
on_list.sort()
return on_listСортировка слиянием связей
Идея
Медленный указатель, который перемещается на одно звено, и быстрый указатель, который перемещается на два звена, находят середину за один проход. Для слияния двух отсортированных списков нужны только их первые узлы: выбери меньший и перейди к следующему. Ни один из этих шагов не требует второго массива.
В первом примере slow останавливается на 3, а разрыв его звена делит 4, 2, 3, 5, 1 на 4, 2, 3 и 5, 1. После сортировки получаются 2, 3, 4 и 1, 5, а при слиянии берутся 1, 2, 3, 4, затем добавляется оставшийся 5.
На каждом уровне разделения каждый узел обрабатывается постоянное число раз, а уровней примерно log n, поэтому время выполнения составляет O(n log n). Дополнительная память нужна только для стека рекурсии: для 4000 узлов его глубина составляет около 12 вызовов.
Алгоритм
- Если в списке один узел (
next[head] == -1), вернитеhead. - Задайте
slow = headиfast = next[head]; перемещайтеslowна одну ссылку, аfast— на две, покаfastиnext[fast]не равны-1. - Пусть
second = next[slow], затем разорвите список, задавnext[slow] = -1. - Рекурсивно отсортируйте обе половины. Объедините их: связывайте меньший первый узел после
tail, пока одна из половин не опустеет, а затем присоедините остаток другой половины. - Пройдите по списку от возвращённой головы и соберите значения.
def sortList(next, values):
def merge(a, b):
# Splice two sorted lists into one; on a tie the node from a goes first.
head = tail = -1
while a != -1 and b != -1:
if values[b] < values[a]:
node, b = b, next[b]
else:
node, a = a, next[a]
if tail == -1:
head = node
else:
next[tail] = node
tail = node
next[tail] = a if a != -1 else b # attach whatever is left
return head
def sort(head):
if next[head] == -1: # one node is already sorted
return head
# slow stops on the last node of the first half
slow, fast = head, next[head]
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
second = next[slow]
next[slow] = -1 # cut the list in two
return merge(sort(head), sort(second))
result = []
node = sort(0)
while node != -1:
result.append(values[node])
node = next[node]
return result
Ловушки и крайние случаи
- Сортировка всего массива
values. Во втором примере она добавляет9и5, которых нет в списке. - Запуск
fastс головы списка. При двух узлахslowзатем оказывается на втором узле, разделение оставляет вторую половину пустой, и рекурсия не сокращает список. - Если забыть о разделении
next[slow] = -1, первая половина затем переходит во вторую, и оба вызова сортируют пересекающиеся списки. - Отбрасывание оставшейся части половины, когда другая заканчивается. Эти узлы исчезают из результата.
- В Lua и R массивы начинаются с 1: сохраняйте индексы узлов с отсчётом от 0 и читайте
next[node + 1]. Версия на R один раз копирует массив ссылок, поэтому использует O(n) дополнительной памяти.
Частые вопросы3
Как лучше всего отсортировать связанный список?
Сортировка слиянием. Разбиение посередине, сортировка обеих половин и их слияние выполняются проходом по списку вперёд — это единственное направление, поддерживаемое односвязным списком. Алгоритм работает за время O(n log n) и повторно связывает существующие узлы.
Почему для связанных списков предпочтительнее сортировка слиянием, а не быстрая сортировка?
Быстрая сортировка может разбить список на части, изменяя связи между элементами, но для хорошего опорного элемента нужен произвольный доступ, а выбор первого элемента в качестве опорного приводит к тому, что сортировка упорядоченного списка требует O(n²). Сортировка слиянием всегда делит список пополам, поэтому её сложность остаётся O(n log n) для любых входных данных.
Можете ли вы отсортировать связный список за время O(n log n) и используя O(1) памяти?
Да, с помощью восходящей сортировки слиянием. Она объединяет соседние серии длиной 1, затем 2, затем 4, пока одна серия не охватит весь список. Выполняется log n линейных проходов, а из памяти нужны только несколько индексов узлов.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
def sortList(next, values):
# Напишите код здесьТест #1
Тест #2
Тест #3
Аргументы
next = [3, -1, 4, 2, 1] values = [4, 1, 3, 2, 5]
Ожидаемый вывод
[1, 2, 3, 4, 5]