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

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

Пример:

Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"] Output: "steps"

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

1⃣Создаем фиктивный узел dummy и указатель cur, указывающий на него.

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

3⃣После выхода из цикла, добавляем оставшиеся элементы от одного из списков (если остались).

😎 Решение:

class Solution { 
public: 
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { 
        ListNode* dummy = new ListNode(0); 
        ListNode* cur = dummy; 

        while (list1 && list2) { 
            if (list1->val > list2->val) { 
                cur->next = list2; 
                list2 = list2->next; 
            } else { 
                cur->next = list1; 
                list1 = list1->next; 
            } 
            cur = cur->next; 
        } 

        cur->next = list1 ? list1 : list2; 

        return dummy->next;         
    } 
};

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