----- Условие ----- Даны два отсортированных связных списка. Требуется объединить в один отсортированный список.

----- Решение ----- 1) Устанавливаем первый узел: берем с наименьшим val из первых узлов списков, сдвигаем указатель списка, значение которого было использовано. 2) В цикле проходимся по спискам до тех пор, пока один из них не закончится, устанавливая next результирующего списка на узел с меньшим значением и сдвигая указатель списка, значение которого было использовано. В результате list1 и list2 сокращаются, а newList заполняется отсортированными узлами. 3) Оставшуюся часть непустого списка добавляем в результирующий.

Сложность алгоритма по времени O(n + m), где n и m - длины списков, сложность по памяти O(1), так как мы не создаем новых узлов, а лишь переиспользуем текущие.

----- Код ----- /**  * Definition for singly-linked list.  * function ListNode(val, next) {  *     this.val = (val===undefined ? 0 : val)  *     this.next = (next===undefined ? null : next)  * }  */ /**  * @param {ListNode} list1  * @param {ListNode} list2  * @return {ListNode}  */ const mergeTwoLists = function(list1, list2) {   if (!list1 && !list2) return null;   if (list1 && !list2) return list1;   if (list2 && !list1) return list2;     let newList;

if (list1.val < list2.val) {     newList = list1;     list1 = list1.next;   } else {     newList = list2;     list2 = list2.next;   }

let newListTail = newList;

while (list1 && list2) {     if (list1.val > list2.val) {       newListTail.next = list2;       list2 = list2.next;     } else {       newListTail.next = list1;       list1 = list1.next;     }

newListTail = newListTail.next;   }

newListTail.next = list1 ? list1 : list2;

return newList; };