4. Merge K Sorted Lists

«Разделяй и властвуй — это не просто военная тактика, это единственный способ победить комбинаторный взрыв».
— Брайан Керниган

Слияние K отсортированных списков (Merge K Sorted Lists): приоритетные очереди и Divide & Conquer

Задача Merge K Sorted Lists (LeetCode 23) — эталонная проверка навыков работы со связными списками и приоритетными очередями.
Дан массив из $K$ односвязных списков, каждый из которых уже упорядочен по возрастанию. Требуется объединить их в один общий отсортированный связный список.

Пусть $N$ — общее число узлов во всех $K$ списках.

• Наивное последовательное слияние (список $1$ со списком $2$, затем результат со списком $3$ и т.д.) дает худшую сложность $O(K \times N)$ — каждый узел участвует в сравнениях до $K$ раз.
• Оптимальные алгоритмы снижают время до $O(N \log K)$.

flowchart TD
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc
    classDef error   fill:#7f1d1d,stroke:#f87171,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc

    A["Инициализация: поместить головы всех непустых списков в Min-Heap"]:::entry --> B{"Куча пуста?"}:::warning
    B -->|"Да"| C["Вернуть голову результирующего списка dummy.Next"]:::success
    B -->|"Нет"| D["Извлечь минимальный узел: minNode = heap.Pop()"]:::process
    D --> E["Присоединить minNode к хвосту результата:<br/>tail.Next = minNode"]:::process
    E --> F{"minNode.Next != nil ?"}:::warning
    F -->|"Да"| G["heap.Push(minNode.Next)"]:::process
    F -->|"Нет"| B
    G --> B
  

1. Стратегия 1: Приоритетная очередь (Min-Heap)

Мы заводим минимальную кучу емкостью $K$, в которую помещаем головы всех доступных списков.

1. Извлекаем из кучи глобально минимальный узел за $O(\log K)$ и прикрепляем его к результирующему списку.
2. Если у извлеченного узла есть следующий элемент (minNode.Next != nil), помещаем его в кучу за $O(\log K)$.
3. Повторяем, пока куча не опустеет.

Итоговое время: ровно $N$ извлечений и $N$ вставок в кучу размера $K$ — сложность строго $O(N \log K)$.
Память: $O(K)$ для хранения указателей в срезе кучи.

package mergek

import (
    "container/heap"
)

// ListNode представляет узел односвязного списка
type ListNode struct {
    Val  int
    Next *ListNode
}

// nodeHeap реализует интерфейс heap.Interface для среза указателей
type nodeHeap []*ListNode

func (h nodeHeap) Len() int           { return len(h) }
func (h nodeHeap) Less(i, j int) bool { return h[i].Val < h[j].Val } // Min-Heap
func (h nodeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *nodeHeap) Push(x any) {
    *h = append(*h, x.(*ListNode))
}

func (h *nodeHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// MergeKLists объединяет K отсортированных списков через Min-Heap
func MergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }

    h := make(nodeHeap, 0, len(lists))
    for _, head := range lists {
        if head != nil {
            h = append(h, head)
        }
    }
    heap.Init(&h)

    dummy := &ListNode{}
    tail := dummy

    for h.Len() > 0 {
        smallest := heap.Pop(&h).(*ListNode)
        tail.Next = smallest
        tail = tail.Next

        if smallest.Next != nil {
            heap.Push(&h, smallest.Next)
        }
    }

    return dummy.Next
}

2. Стратегия 2: Попарное слияние (Divide & Conquer)

Вместо использования кучи можно объединять списки парами по принципу турнирной сетки:

• На первом раунде сливаем: lists[0] с lists[1], lists[2] с lists[3] и т.д. Число списков уменьшается вдвое: $K \to \lceil K/2 \rceil$.
• Повторяем раунды слияния до тех пор, пока не останется ровно один объединенный список.

Число уровней дерева слияния равно $\lceil \log_2 K \rceil$.
На каждом уровне каждый из $N$ узлов участвует в слиянии ровно один раз.
Сложность по времени: $O(N \log K)$.
Память: $O(1)$ при итеративной реализации (без рекурсивного стека).

func MergeKListsDivideConquer(lists []*ListNode) *ListNode {
    k := len(lists)
    if k == 0 {
        return nil
    }

    interval := 1
    for interval < k {
        for i := 0; i+interval < k; i += interval * 2 {
            lists[i] = mergeTwoLists(lists[i], lists[i+interval])
        }
        interval *= 2
    }

    return lists[0]
}

func mergeTwoLists(l1, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy

    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            tail.Next = l1
            l1 = l1.Next
        } else {
            tail.Next = l2
            l2 = l2.Next
        }
        tail = tail.Next
    }

    if l1 != nil {
        tail.Next = l1
    } else {
        tail.Next = l2
    }

    return dummy.Next
}

3. Сравнение подходов на практике

4. Вопросы для собеседования

Резюме

1. Наивное последовательное слияние неэффективно и дает сложность $O(K \times N)$.
2. Алгоритмы на базе Min-Heap и Divide & Conquer сокращают время до строгого $O(N \log K)$.
3. Min-Heap является стандартом для потокового онлайн-слияния, а Divide & Conquer обеспечивает наименьший расход памяти $O(1)$.

В следующей статье мы перейдем к монотонному стеку и задаче поиска максимального прямоугольника в гистограмме: 5. Largest Rectangle in Histogram.