Merge Two Sorted Lists

Условие

Даны два отсортированных по возрастанию связанных списка. Необходимо слить их в один отсортированный список и вернуть его.

Примеры

Input: list1 = [1, 2, 4], list2 = [1, 3, 4]

Output: [1, 1, 2, 3, 4, 4]

Input: list1 = [], list2 = []

Output: []

Input: list1 = [], list2 = [0]

Output: [0]

Решение

// Определение структуры узла связанного списка
class ListNode(var value: Int) {
    var next: ListNode? = null
}

fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
    // Создаем новый пустой узел для начала объединенного списка
    var dummy = ListNode(0)
    var current = dummy

    // Пока оба списка непустые, продолжаем сравнивать их элементы
    var p1 = list1
    var p2 = list2

    while (p1 != null && p2 != null) {
        if (p1.value <= p2.value) {
            // Если значение в первом списке меньше или равно, добавляем его в результат
            current.next = p1
            p1 = p1.next
        } else {
            // Если значение во втором списке меньше, добавляем его в результат
            current.next = p2
            p2 = p2.next
        }
        // Переходим к следующему узлу результата
        current = current.next!!
    }

    // Добавляем оставшиеся элементы, если один из списков пуст
    current.next = p1 ?: p2

    // Возвращаем объединенный список (пропуская вспомогательный узел)
    return dummy.next
}

Временная сложность

O(n + m), где n и m — количество элементов в списках list1 и list2, так как мы проходим по каждому элементу обоих списков один раз.

Пространственная сложность

O(1), если не учитывать память, выделенную под новый список. Мы используем фиксированное количество дополнительных переменных.