Эта задача попалась мне на одном из собеседований. Основная сложность в ее решении — нужно четко понимать, что за структура такая cвязный список.
Такая структура данных состоит из элементов, которые называются узлами. Каждый узел содержит две основные части:
1. Значение которое хранит узел. Это может быть число, символ, строка, другая структура данных или даже объект сложного типа.
2. Указатель на следующий, и иногда предыдущий, узел, который "связывает" узлы вместе, позволяя последовательно переходить от одного узла к другому.
Связные списки бывают:
- Односвязные: каждый узел содержит ссылку только на следующий узел. Последний узел указывает на нулевой указатель - конец списка.
- Двусвязные: каждый узел содержит ссылки как на следующий, так и на предыдущий узлы, что позволяет двигаться по списку как вперед, так и назад. Первый узел не имеет предыдущего узла, а последний узел не имеет следующего.
- Кольцевые: последний узел содержит ссылку на первый узел, образуя замкнутый круг.
Задача: Даны два односвязных списка. Значения в списках упорядочены. Нужно смержить (слить в один список) эти списки, чтобы значения также были упорядочены. Вернуть результат. Списки могут быть пустыми.
Подготовка
Создадим структуру ListNode и в функции main подготовим тестовые кейсы.
Решение 1 (через рекурсию)
Cравниваем головные элементы каждого списка и выбираем меньшее из двух для добавления к результату. Процесс продолжается для оставшихся элементов списков.
1. Если list1 пуст, возвращаем list2, потому что нет элементов для слияния, и наоборот.
2. Сравниваем значения Val текущих узлов list1 и list2.
3. Находим узел с меньшим значением. Устанавливаем его Next на результат рекурсивного вызова функции слияния для остальной части этого списка Next и второго списка.
4. Возвращаем выбранный узел, который является головой нового списка.
Рекурсивное решение работает за линейное время, так как каждый вызов функции обрабатывает один элемент из одного из списков. Но такой подход может быть неэффективен по памяти из-за стека вызовов. Особенно если списки очень длинные — это может привести к переполнению стека вызовов.
Решение 2
Данное решение длиннее, но эффективнее по памяти. Список не требует дополнительного пространства для хранения элементов, за исключением временных переменных.
1. Создаем временный узел dummy "пустышку". Он упрощает вставку элементов в новый список, поскольку всегда будет "предыдущий" узел, к которому присоединяем следующий узел.
2. Переменная current будет использоваться для итерации по новому связанному списку. Изначально она указывает на dummy, чтобы начать вставку элементов с "пустышки".
3. Цикл for продолжается до тех пор, пока оба исходных списка (list1 и list2) не будут полностью пройдены. В каждой итерации сравниваются значения текущих узлов двух списков и выбираем меньшее для добавления в current.
4. После завершения цикла, один из списков (list1 или list2) может все еще содержать узлы (если один список был длиннее другого). В этом случае оставшиеся узлы просто добавляются в конец нового списка, так как они уже упорядочены.
5. В конце возвращаем dummy.Next, который является началом нового упорядоченного связанного списка (мы пропускаем искусственно созданный узел "пустышку").
Это все. Удачи на собеседовании!
