Объединение двух отсортированных списков
Даны два отсортированных односвязных списка list1 и list2. Объедините их в один отсортированный список и верните его начало.
Ограничения:
- Длина каждого списка:
0 <= длина <= 100. - Значение узла:
-100 <= Node.val <= 100.
Пример 1:
Input: list1 = [1, 2, 4], list2 = [1, 3, 5] Output: [1, 1, 2, 3, 4, 5]
Пример 2:
Input: list1 = [], list2 = [] Output: []
Рекомендуемая временная и пространственная сложность
Вам следует стремиться к решению с временной сложностью O(n + m) и пространственной сложностью O(1)
для итеративного подхода или O(n + m) для рекурсивного подхода, где n и m —
длины списков.
Подсказка 1
Решение грубой силы заключалось бы в создании нового списка и копировании элементов из обоих списков в правильном
порядке. Это было бы решение с временной сложностью O(n + m) и пространственной сложностью O(n +
m). Можете ли вы придумать более эффективный способ?
Подсказка 2
Можно ли объединить списки, изменяя ссылки между узлами, без использования дополнительной памяти?
Подсказка 3
Используйте два указателя для обхода списков и объединяйте узлы, выбирая меньший элемент на каждом шаге.