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

Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания. Объедините все связанные списки в один отсортированный связанный список и верните его.

Пример:

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

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

1⃣Используем min-heap для хранения текущих головных узлов всех списков.

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

3⃣Повторяем, пока куча не пуста, возвращаем голову объединенного списка.

😎Решение:

class ListNode {
    var val: Int
    var next: ListNode?
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
    var heap = [ListNode]()
    
    for list in lists {
        if let node = list {
            heap.append(node)
        }
    }
    
    heap.sort { $0.val < $1.val }
    
    let dummy = ListNode(0)
    var current: ListNode? = dummy
    
    while !heap.isEmpty {
        let smallest = heap.removeFirst()
        current?.next = smallest
        current = smallest
        
        if let next = smallest.next {
            var index = heap.firstIndex { $0.val > next.val } ?? heap.count
            heap.insert(next, at: index)
        }
    }
    
    return dummy.next
}

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