Объединение двух отсортированных односвязных списков

Условие

Даны указатели на первые узлы двух отсортированных по возрастанию односвязных списков: firstList и secondList. Требуется построить один общий список, также упорядоченный по возрастанию. При этом необходимо собрать результат, переиспользуя узлы из исходных списков, без создания новых объектов.

Ответ

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

Для Node с полями value и next:

Node* merge(Node* a, Node* b) {
    Node* head = nullptr;
    Node** tail = &head;
    while (a && b) {
        Node*& current = a->value <= b->value ? a : b;
        *tail = current;
        current = current->next;
        tail = &((*tail)->next);
    }
    *tail = a ? a : b;
    return head;
}

Время O(n + m), дополнительная память O(1). Предполагаются ациклические списки без общих узлов; исходные связи изменяются. Если списки разделяют хвост или содержат цикл, этот контракт нужно сначала изменить.