Слияние списков

Постановка задачи

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

[1, 1, 2, 3, 4, 4]

list1 = []
list2 = []

[]

list1 = []
list2 = [0]

[0]

Решение

Эта задача проверяет базовую работу со связными списками. У нас уже есть два отсортированных списка, поэтому не нужно ничего сортировать заново. Достаточно идти по обоим спискам и каждый раз выбирать меньший текущий узел.

Идея решения:

Будем держать два указателя: list1 и list2. Они указывают на первые еще не использованные узлы списков.

Для удобства создадим фиктивный узел dummy. Он не является частью ответа, но помогает не обрабатывать отдельно случай, когда мы добавляем первый узел. Указатель tail всегда будет указывать на последний узел уже собранного списка.

На каждом шаге сравниваем list1.val и list2.val:

1. Если значение в list1 меньше или равно значению в list2, добавляем этот узел в результат.
2. Иначе добавляем узел из list2.
3. Сдвигаем указатель того списка, откуда взяли узел.
4. Сдвигаем tail на добавленный узел.

Когда один список закончится, второй можно присоединить целиком. Он уже отсортирован, и все его оставшиеся узлы больше или равны тем, которые мы уже добавили.

Основные шаги:

1. Создаем dummy и tail.
2. Пока оба списка list1 и list2 не пусты, выбираем меньший текущий узел.
3. Прицепляем выбранный узел к tail.next.
4. Сдвигаем указатель выбранного списка и tail.
5. Присоединяем остаток непустого списка.
6. Возвращаем dummy.next.

Рассмотрим пример:

list1 = 1 -> 2 -> 4
list2 = 1 -> 3 -> 4

1. Инициализация: создаем dummy, tail указывает на него. Сравниваем головы списков.

2. 1 <= 1, берем узел из list1. tail сдвигается на добавленный узел.

3. 2 > 1, берем узел из list2.

4. 2 < 3, берем узел из list1.

5. 4 > 3, берем узел из list2.

6. 4 <= 4, берем узел из list1. После этого list1 закончился - прицепляем остаток list2 целиком.

Итог: 1 -> 1 -> 2 -> 3 -> 4 -> 4. Возвращаем dummy.next.

Оценка сложности

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

Каждый узел из обоих списков посещается ровно один раз. Если в первом списке n узлов, а во втором m, временная сложность равна O(n + m).

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

Мы не создаем новые узлы для ответа, а переиспользуем существующие. Дополнительная память равна O(1).

Код решения

Приведем код решения.

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy
 
    for list1 != nil && list2 != nil {
        if list1.Val <= list2.Val {
            tail.Next = list1
            list1 = list1.Next
        } else {
            tail.Next = list2
            list2 = list2.Next
        }
        tail = tail.Next
    }
 
    if list1 != nil {
        tail.Next = list1
    } else {
        tail.Next = list2
    }
    return dummy.Next
}

Итоги

Задача Merge Two Sorted Lists - это базовый пример слияния двух отсортированных последовательностей, только вместо индексов мы двигаем указатели по узлам.

1. Суть алгоритма: мы сравниваем текущие головы двух списков и каждый раз добавляем меньший узел в конец результата.
2. Эффективность:
   • Временная сложность: O(n + m), так как каждый узел обрабатывается один раз.
   • Пространственная сложность: O(1), так как мы переиспользуем узлы исходных списков.
3. Граничные случаи:
   • Оба списка пустые: dummy.next останется null.
   • Один список пустой: результатом будет второй список.
   • Значения равны: можно брать узел из любого списка, порядок все равно останется корректным.
4. Оптимальное решение: использует уже заданную сортировку и делает один линейный проход без дополнительного списка.