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

Question

Мне удалось выяснить, как объединить два отсортированных списка в порядке возрастания, но мне не удается найти способ сделать это в противоположном направлении.Как я могу объединить два списка в один в порядке убывания, не переворачивая строку после?

Answer 1

Вы просто должны сделать все противоположным образом - извлечь элементы из хвоста вместо головы, выбрать большее из двух при сравнении и вернуть оставшийся список в обратном порядке, когда другой исчерпан:

def merge(lst1, lst2):
    if not lst1:
        return lst2[::-1]
    if not lst2:
        return lst1[::-1]
    if lst1[-1] < lst2[-1]:
        return [lst2[-1]] + merge(lst1, lst2[:-1])
    else:
        return [lst1[-1]] + merge(lst1[:-1], lst2)

, чтобы:

 merge([2,5,9,12], [0,1,3,4,8])

вернулось:

 [12, 9, 8, 5, 4, 3, 2, 1, 0]