Объединить 2 отсортированных списков

Question

Меня попросили найти как можно больше решений для следующей проблемы:

Напишите функцию, которая принимает два списка чисел (оба предполагаются в порядке возрастания) и объединяет их в единый список (также в в порядке возрастания).

Моими первыми решениями было append list1 на list2, а затем повторно sort.

Тогда я нашел встроенный merge.

Затем я решил реализовать решение самостоятельно и придумал хвостовую рекурсивную функцию, которая на данный момент работает только для подмножества списков.

Сама проблема выглядит так, как будто у меня, наконец, есть причина читать Кнут, но увы, Uni и Библиотека закрыты из-за снега.

Итак, я обращаюсь к вам ТАК, какие есть интересные, эффективные или анти-шаблонные подходы к этой проблеме?

---

P.S Я не ищу реализации, если это не лучший способ продемонстрировать идею. Я просто смотрю, как люди подошли к этому типу проблемы.

Answer 1

Вы можете написать функцию is-sorted-p, которая определяет, находится ли список в порядке возрастания. Затем объедините два списка и случайным образом перемешайте результат, пока он не пройдет ваш предикат.

... Вы ничего не сказали о производительности.

Answer 2

Объединение двух отсортированных списков алгоритмически тривиально.

Начните с первого элемента каждого списка, сравните, запишите нижний для вывода и продвиньте список, в котором вы нашли нижний.Продолжайте, пока не дойдете до конца одного списка, затем потушите остаток от другого списка.

Для этого требуется всего один цикл над каждым списком и макс.одно сравнение для каждого выходного элемента.

Редактировать: это так же эффективно, как и для двух списков.Это становится немного сложнее, когда вам нужно объединить большое количество списков.

Answer 3

Если у вас ровно два, это относительно просто.

1. Являются ли оба списка пустыми?Если это так, результатом будет пустой список
2. Один список пуст, а другой нет?Результатом является непустой список.
3. Найдите наименьший заголовок списка ("машина"), в результате этот заголовок списка приравнивается к результату самостоятельного вызова с хвостом этого списка идругой список.

Это можно преобразовать в хвостовой рекурсивный процесс, используя некоторые вспомогательные параметры (и, возможно, пользовательскую вспомогательную функцию "назад и против").

Answer 4

Существует несколько способов решения этой проблемы.

Поскольку существует два связанных списка, и так как оба отсортированы самым простым способом на высоком уровне, игнорируя базовые случаи.Для дальнейшей оптимизации мы можем сделать insert_sort для повторной установки позиции, в которой произошла вставка, чтобы избежать вставок, происходящих с начала каждый раз.Потому что в худшем случае это может занять O (m * n) временной сложности, если все элементы второго связанного списка вставляются ближе к концу 1-го списка.

Answer 5

Если ваши списки могут удваиваться как сбалансированные двоичные деревья , вы можете вставить все элементы от list2 до b-tree(list1) и преобразовать обратно в список.

Answer 6

Вы ищете рекурсивное определение функции, которая создает список (объединяя два списка).

Следует ожидать, что функция создаст список, извлекая элемент head в соответствии с некоторым принципом, а затем рекурсивно формируя хвост списка из оставшихся элементов.

Поскольку вам нужно вернуть отсортированный список, заголовок списка всегда является наименьшим элементом списка. Итак, все, что вам нужно сделать, это найти алгоритм, который извлекает наименьший элемент из двух отсортированных списков (что должно быть довольно просто, поскольку они отсортированы).