Задача: №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.
- Если list1.val <= list2.val, связываем list1.next с результатом mergeTwoLists(list1.next, list2)
- Иначе — делаем то же самое для list2

3️⃣ Возвращаем голову текущего минимального узла как новый корень объединённого списка.

😎 Решение:

var mergeTwoLists = function (list1, list2) {
    if (!list1 || !list2) {
        return list1 || list2;
    }

    if (list1.val <= list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
};

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