Функция, объединяющая несколько отсортированных связанных списков

Условие

Необходимо написать функцию, которая принимает массив из k отсортированных по возрастанию связанных списков и формирует из них один общий связный список, сохраняющий порядок возрастания. Функция должна вернуть полученный список.

Пример: Вход: sequences = [[1, 4, 5], [1, 3, 4], [2, 6]] Вывод: [1, 1, 2, 3, 4, 4, 5, 6]

Ответ

Используйте min-heap из текущих голов непустых списков. Извлекайте минимальный узел, присоединяйте к результату и добавляйте в кучу его следующий узел.

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

Node* mergeLists(const std::vector<Node*>& lists) {
    auto later = [](Node* a, Node* b) { return a->value > b->value; };
    std::priority_queue<Node*, std::vector<Node*>, decltype(later)> heap(later);
    for (Node* node : lists) if (node) heap.push(node);
    Node* head = nullptr;
    Node** tail = &head;
    while (!heap.empty()) {
        Node* node = heap.top();
        heap.pop();
        if (node->next) heap.push(node->next);
        *tail = node;
        tail = &node->next;
    }
    *tail = nullptr;
    return head;
}

Нужны и . Списки должны быть ациклическими и не разделять узлы. Алгоритм переиспользует и перелинковывает узлы; время O(N log k) при k > 1, память O(k). Для одного списка достаточно вернуть его голову.