Объединение списков

Дан массив из N связных списков. Каждый список уже отсортирован по возрастанию. Объединить их все в один большой отсортированный список.

Input lists:
1 -> 7 -> 24
3 -> 5 -> 17
-3 -> 19

Output:
-3 -> 1 -> 3 -> 5 -> 7 -> 17 -> 19 -> 24

Вариант 1 (Простой): Попарный merge. Объединяем списки по очереди. Сложность растёт.
Вариант 2 (Эффективный): Использовать Min-Heap (приоритетную очередь). Кладём головы всех списков в кучу. Достаём минимум, добавляем в результат, кладём next из того же списка в кучу. Сложность O(K log N), где K — общее число элементов.