Задача: №21. Merge Two Sorted Lists
Сложность: easy

Вам даны заголовки двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем сращивания узлов первых двух списков. Возвращает заголовок объединенного связанного списка.

Пример:

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

👨‍💻 Алгоритм:

1⃣Если один из списков пуст, вернуть другой список.

2⃣Сравнивать значения узлов list1 и list2, выбирая меньший узел для объединенного списка.

3⃣Рекурсивно продолжать объединение, связывая меньший узел с результатом mergeTwoLists от оставшихся узлов.

😎 Решение:

class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        guard let list1 = list1 else { return list2 }
        guard let list2 = list2 else { return list1 }
        
        if list1.val < list2.val {
            list1.next = mergeTwoLists(list1.next, list2)
            return list1
        } else {
            list2.next = mergeTwoLists(list1, list2.next)
            return list2
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний