Слияние отсортированных списков

Решение

Задача требует объединения двух отсортированных списков в один отсортированный результат. Это классическая задача, которая часто встречается на собеседованиях и тесно связана с алгоритмом merge из сортировки MergeSort.

Подход с двумя указателями (Two-Pointer Technique)

Оптимальное решение использует технику двух указателей с временной сложностью O(n + m), где n и m — длины списков. Идея проста: проходим оба списка одновременно, сравниваем элементы и добавляем меньший в результат.

def merge_sorted_lists(list1: list[int], list2: list[int]) -> list[int]:
    """
    Объединяет два отсортированных списка в один отсортированный список.
    
    Args:
        list1: Первый отсортированный список
        list2: Второй отсортированный список
    
    Returns:
        Объединённый отсортированный список
    
    Time Complexity: O(n + m)
    Space Complexity: O(n + m)
    """
    result = []
    i, j = 0, 0
    
    # Проходим оба списка, сравнивая элементы
    while i < len(list1) and j < len(list2):
        if list1[i] <= list2[j]:
            result.append(list1[i])
            i += 1
        else:
            result.append(list2[j])
            j += 1
    
    # Добавляем оставшиеся элементы из первого списка
    result.extend(list1[i:])
    
    # Добавляем оставшиеся элементы из второго списка
    result.extend(list2[j:])
    
    return result

Примеры использования

# Базовый пример
list1 = [1, 3, 5]
list2 = [2, 4, 6]
print(merge_sorted_lists(list1, list2))  # [1, 2, 3, 4, 5, 6]

# Списки разной длины
list1 = [1, 2, 5]
list2 = [3, 4, 6, 7, 8]
print(merge_sorted_lists(list1, list2))  # [1, 2, 3, 4, 5, 6, 7, 8]

# Один список длиннее
list1 = [1, 10]
list2 = [2, 3, 4, 5]
print(merge_sorted_lists(list1, list2))  # [1, 2, 3, 4, 5, 10]

# Пустые списки
list1 = []
list2 = [1, 2, 3]
print(merge_sorted_lists(list1, list2))  # [1, 2, 3]

Альтернативные подходы

Простой способ (не оптимальный):

def merge_sorted_lists_simple(list1: list[int], list2: list[int]) -> list[int]:
    return sorted(list1 + list2)  # O(n log n)

Этот способ работает, но менее эффективен — O(n log n) вместо O(n + m).

Ключевые характеристики решения

• Временная сложность: O(n + m) — каждый элемент посещается ровно один раз
• Пространственная сложность: O(n + m) — для хранения результата
• Стабильность: Сохраняет относительный порядок элементов
• Надёжность: Работает с пустыми списками, списками разной длины, дубликатами

Это решение идеально подходит для QA автоматизации, так как демонстрирует понимание алгоритмов и умение писать эффективный, читаемый код.