Вопрос:

Вам даны заголовки двух отсортированных связанных списков list1 и list2.

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

Возвращает заголовок объединенного связанного списка.

Пример 1:

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

Ограничения:

  • Количество узлов в обоих списках находится в диапазоне [0, 50].
  • -100 <= Node.val <= 100
  • И list1, и list2 отсортированы в неубывающем порядке.

Решение:

В данной задаче есть два связанных списка, которые уже отсортированы. Поэтому нам просто нужно сравнить значения обоих списков и объединить их.

Наш первый шаг — проверить, пусты ли списки. Если один из них пуст или нулевой, то верните другой список.

if(list1 == NULL)
    return list2;
if(list2 == NULL)
    return list1;

Следующим шагом является сравнение значений обоих списков.

Если значение списка1 меньше или равно значению списка2, мы возьмем следующий указатель списка1 вместе со списком2 и передадим их в качестве аргументов в функции mergeTwoLists(). И список1 будет возвращен.

if(list1 -> val <= list2 -> val)
    {
        list1 -> next = mergeTwoLists(list1 -> next, list2);
            return list1;
       }

Теперь нам нужно написать другое условие.

Если значение list1 больше, чем значение list2, мы будем передавать list1 и значение следующего указателя list2 в качестве аргументов в функции mergeTwoLists(). список2 будет возвращен.

list2 -> next = mergeTwoLists(list1, list2 -> next);
    return list2;

Ниже приведен полный код данной проблемы:

Спасибо за чтение!

S.