Задача: №23. Merge k Sorted Lists
Сложность: hard

Дан массив из k отсортированных связанных списков.
Нужно объединить их в один отсортированный связанный список и вернуть его голову.

Пример:

Input: lists = [[1,4,5],[1,3,4],[2,6]]  
Output: [1,1,2,3,4,4,5,6]

👨‍💻 Алгоритм:

1️⃣ Создаем мин-кучу (приоритетную очередь), в которую помещаем первые узлы всех непустых списков.
Приоритет — по значению узла.

2️⃣ Извлекаем узел с минимальным значением из очереди, присоединяем его к результирующему списку, а если у него есть следующий узел — добавляем его в очередь.

3️⃣ Повторяем, пока очередь не опустеет. В итоге получаем отсортированный список.

😎 Решение:

var mergeKLists = function (lists) {
    const pq = new MinPriorityQueue({ priority: node => node.val });

    for (const head of lists) {
        if (head) pq.enqueue(head);
    }

    const dummy = new ListNode();
    let cur = dummy;

    while (!pq.isEmpty()) {
        const node = pq.dequeue().element;
        cur.next = node;
        cur = cur.next;

        if (node.next) pq.enqueue(node.next);
    }

    return dummy.next;
};

Ставь 👍 и забирай 📚 Базу знаний