Merge Two Sorted Lists

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

Это O(L1 + L2) : каждое сравнение помещает один узел, и ни один узел не помещается дважды. При использовании объектов узлов для слияния требуется дополнительная память O(1) , поскольку оно только меняет ссылки. В случае массивов, используемых здесь, общий массив ссылок требует памяти O(L1 + L2) .

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

+10

Тебе даны два односвязных списка, каждый хранится в двух массивах одинаковой длины. В первом списке узел i содержит значение values1[i] и указывает на узел next1[i]. Второй список устроен так же, с next2 и values2. В обоих списках -1 обозначает конец списка, а голова — это узел 0. Узлы хранятся не в порядке следования в списке, поэтому переходи по ссылкам.

Значения в каждом списке расположены вдоль ссылок в неубывающем порядке. Объедини списки в один отсортированный список и верни его значения по порядку.

Функция

mergeTwoLists(next1: integer-array, values1: integer-array, next2: integer-array, values2: integer-array) → integer-array

next1integer-array: индекс узла, на который ссылается каждый узел первого списка, или -1 для его последнего узла
values1integer-array: значение, хранящееся в каждом узле первого списка
next2integer-array: индекс узла, на который ссылается каждый узел второго списка, или -1 для его последнего узла
values2integer-array: значение, хранящееся в каждом узле второго списка
Возвращаетinteger-array: значения объединённого списка по порядку

Ограничения

1 ≤ L1 ≤ 2000, где L1 — длина next1 и values1.
1 ≤ L2 ≤ 2000, где L2 — длина next2 и values2.
-1000 ≤ values1[i], values2[j] ≤ 1000
Каждый элемент next1 — это -1 или индекс узла первого списка, а каждый элемент next2 — это -1 или индекс узла второго списка.
Начиная с узла 0, каждый список посещает каждый из своих узлов ровно один раз, а затем достигает -1. Цикла нет.
Вдоль своих связей каждый список отсортирован в порядке неубывания.

Примеры

Ввод: next1 = [2, -1, 1]values1 = [1, 6, 4]next2 = [3, 2, -1, 1]values2 = [2, 7, 9, 3]
Вывод: [1, 2, 3, 4, 6, 7, 9]
Пояснение: Следуя по ссылкам, первый список проходит узлы 0, 2, 1 и считывает значения 1, 4, 6; второй считывает значения 2, 3, 7, 9. Каждый раз выбирая меньшее из первых значений, получаем 1, 2, 3, 4, 6, 7, 9.

Ввод: next1 = [2, -1, 1]values1 = [-3, 5, 0]next2 = [-1]values2 = [0]
Вывод: [-3, 0, 0, 5]
Пояснение: Первый список содержит значения -3, 0, 5, а второй — единственное значение 0. Оба значения 0 остаются в результате, поэтому в нём четыре значения.

Ввод: next1 = [1, -1]values1 = [8, 10]next2 = [2, -1, 1]values2 = [1, 3, 2]
Вывод: [1, 2, 3, 8, 10]
Пояснение: Второй список содержит 1, 2, 3 — все числа меньше 8, с которого начинается первый список. Сначала идёт весь второй список, затем 8, 10.

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

Можешь ли ты объединить k отсортированных списков за время O(N log k), где N — общее количество узлов?

Подсказки

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

Открыто 0 из 3

Решение

Оба списка отсортированы, поэтому наименьшее из оставшихся значений всегда находится в начале одного из них. Сравни два первых элемента, добавь меньший к результату и перейди к следующему элементу в этом списке. Можно также отсортировать все N = L1 + L2 значений, но такой подход не учитывает, что списки уже отсортированы, и требует O(N log N).

Помести все значения в один массив и отсортируй его

Идея

Объединённый список — это отсортированная версия всех значений N, поэтому скопируй оба массива значений в один и отсортируй его. Порядок узлов внутри массивов не имеет значения, потому что при сортировке учитывается каждое значение. При N ≤ 4000 это достаточно быстро, но сортировка требует O(N log N) сравнений, тогда как при слиянии нужно не более N-1, а сортировка вообще не затрагивает ссылки — именно этот навык проверяет задача.

Алгоритм

Скопируй values1 и values2 в один массив.
Отсортируй массив в порядке неубывания.
Верни его.

def mergeTwoLists(next1, values1, next2, values2):
    # Sorting puts every value in its place without following a single link.
    return sorted(values1 + values2)

Присоедините узлы после фиктивного головного узла

Идея

Указатель здесь — это индекс узла. Чтобы объединить узлы обоих списков в одну цепочку, присвой им общую нумерацию: узел j списка 2 станет узлом L1+j, а его ссылки сдвинутся так же. Перед результатом стоит фиктивный узел с номером L1+L2.

Храни a и b на первых ещё не использованных узлах каждого списка, а tail — на конце объединённой цепочки. На каждом шаге связывай tail с меньшим из первых узлов и передвигай этот указатель и tail вперёд. Когда один список закончится, оставшаяся часть другого уже отсортирована и связана, поэтому достаточно одного присваивания, чтобы присоединить её. В первом примере узлы списка 2 перенумеровываются с 3 по 6. После узлов 0, 3, 6, 2, 1 список 1 заканчивается, и link[tail] = 4 присоединяет 7, 9.

Каждый узел связывается не более одного раза: время O(N). Общий массив ссылок занимает O(N) памяти, тогда как объекты узлов не потребовали бы памяти.

Алгоритм

Создай один массив ссылок: next1, затем next2 со сдвигом на L1 (оставь -1 без изменений), затем -1 для фиктивного элемента L1+L2. Создай соответствующий массив значений.
Установи a = 0, b = L1, а tail — на фиктивный элемент.
Пока ни a, ни b не равны -1, свяжи tail с меньшим элементом (при равенстве — с a), передвинь соответствующий указатель и перемести tail на этот элемент.
Свяжи tail с тем из a и b, который не равен -1.
Пройди от link[dummy] до -1 и собери значения.

def mergeTwoLists(next1, values1, next2, values2):
    n1 = len(next1)
    n2 = len(next2)
    # One node space: list 2's node j becomes node n1 + j, and node n1 + n2 is a
    # dummy that sits in front of the merged list.
    link = list(next1) + [j + n1 if j != -1 else -1 for j in next2] + [-1]
    value = list(values1) + list(values2)
    dummy = n1 + n2
    tail = dummy  # the last node of the merged list so far
    a = 0  # the first unused node of list 1
    b = n1  # the first unused node of list 2
    while a != -1 and b != -1:
        if value[a] <= value[b]:
            link[tail] = a  # splice a in after the tail
            a = link[a]
        else:
            link[tail] = b  # splice b in after the tail
            b = link[b]
        tail = link[tail]
    # One list ran out. The rest of the other one is sorted and linked already.
    link[tail] = a if a != -1 else b
    merged = []
    node = link[dummy]
    while node != -1:
        merged.append(value[node])
        node = link[node]
    return merged

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

Слияние массивов в порядке индексов. Узлы хранятся в перемешанном порядке, поэтому сам массив values1 не отсортирован: в первом примере это [1, 6, 4]. Отсортирован только обход, начинающийся с узла 0.
Забыть об оставшихся элементах. Когда один список заканчивается, цикл останавливается, и если отбросить остаток другого списка, потеряются наибольшие значения: 7, 9 в первом примере.
Перемещение не того указателя или обоих указателей. Вперёд перемещается только тот список, узел которого вы взяли.
Смешение двух систем нумерации. Узел 2 списка 2 — это не узел 2 списка 1. Сдвиньте индексы и ссылки списка 2 на L1, а -1 оставьте как есть.

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

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

Это O(L1 + L2): каждое сравнение помещает один узел, и ни один узел не помещается дважды. При использовании объектов узлов для слияния требуется дополнительная память O(1), поскольку оно только меняет ссылки. В случае массивов, используемых здесь, общий массив ссылок требует памяти O(L1 + L2).

Зачем использовать фиктивный узел при слиянии связных списков?

Без него для первого узла результата нужен отдельный код, потому что хвоста, за которым его можно связать, ещё нет. Фиктивный узел — это заглушка для головы списка, поэтому первый узел связывается так же, как и все остальные. В конце вы возвращаете следующий узел фиктивного узла, и заглушка исчезает.

Следует ли объединять два отсортированных списка рекурсивно или итеративно?

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

def mergeTwoLists(next1, values1, next2, values2):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

next1 = [2, -1, 1]
values1 = [1, 6, 4]
next2 = [3, 2, -1, 1]
values2 = [2, 7, 9, 3]

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

[1, 2, 3, 4, 6, 7, 9]