Mediumheapmerge
Как слить k отсортированных списков?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
LeetCode 23. Min-heap хранит текущие головы каждого списка; всегда берём минимальный и добавляем следующий из того же списка. O(N log K), где N = total elements, K = lists.
import heapq
def mergeKLists(lists):
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
dummy = cur = ListNode()
while heap:
val, i, node = heapq.heappop(heap)
cur.next = node
cur = cur.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.nextАльтернативы: divide and conquer (merge pairs, log K уровней × O(N) = O(N log K)); sequential merge (O(N·K) — плохо для больших K). В Python нужен counter-tiebreaker, т.к. ListNode не comparable.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.