Почему это работает
- Каждый список отсортирован, поэтому наименьший ещё не привязанный узел — всегда первый неиспользованный узел какого-то списка. В куче лежат ровно такие, по одному на список, поэтому наверху следующий узел ответа.
- У пустого списка нет головы, и он не попадает в кучу; закончившийся список ничего не кладёт, и куча просто уменьшается. Ни то ни другое не требует особого случая дальше.
- Фиктивный узел dummy позволяет привязать первый узел так же, как остальные, поэтому tail.next = node — одна строка на все случаи; узлы перевязываются, а не копируются.
Сложность
Время O(N log k) для N узлов в k списках: каждый узел один раз попадает в кучу не больше чем из k и один раз её покидает. Память O(k) на кучу: ответ собран из тех же узлов.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗