Легкий
Проблема
Объедините два отсортированных связанных списка и верните его как новый список. Новый список должен быть составлен путем соединения узлов первых двух списков.
Пример:
Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4
Решение — итерация
Используйте два указателя для отслеживания двух списков. Сначала сравните l1 с l2 и определите указатели small и large. На каждой итерации мы будем использовать указатель tail для поиска узла, значение которого больше large в списке, в котором находится small. И измените small и large в интерактивном режиме.
Сложность
Наконец, мы пройдем по каждому списку только один раз в этих двух циклах, поэтому временная сложность будет O(m+n), если m и n обозначают количество узлов в этих двух списках. .
Тривиально, что он использует только O(1) дополнительного пространства.
Решение — рекурсия
Выньте первый узел списка, который имеет меньшее значение головного узла, и рекурсивно вызовите себя для остальных двух списков.
Сложность
Понятно, что каждый вызов функции занимает всего O(1) времени и дополнительного места. И может потребоваться вызов функции O (m + n) раз для обхода всех узлов в l1 и l2, если m и n обозначают количество узлов в двух списках. Таким образом, временная и пространственная сложность составляют O(m+n).
