23. Merge k Sorted Lists

Задача

Дан массив из k отсортированных связных списков. Слейте их в один отсортированный список.

Примеры

Пример 1

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

Пояснение

Списки 1→4→5, 1→3→4, 2→6 сливаются в один отсортированный список 1→1→2→3→4→4→5→6.

Пример 2

Input: lists = []
Output: []

Пример 3

Input: lists = [[]]
Output: []

Решение

Решение

// Временная сложность: O(k × N), где k - количество списков, N - общее количество узлов
// Пространственная сложность: O(1) - не считая результат
 
var mergeKLists_Naive = function(lists) {
    // Базовый случай: если массив пустой или null
    if (!lists || lists.length === 0) return null;
 
    // Начинаем с первого списка как результата
    let result = lists[0];
 
    // Последовательно сливаем каждый список с результатом
    // Каждое слияние проходит по всем узлам в обоих списках
    for (let i = 1; i < lists.length; i++) {
        result = mergeTwoLists(result, lists[i]);
    }
 
    return result;
};
 
// Вспомогательная функция: слияние двух отсортированных списков
// Временная сложность: O(n + m), где n и m - длины списков
function mergeTwoLists(l1, l2) {
    // Dummy node упрощает работу с головой списка
    const dummy = new ListNode(0);
    let current = dummy;
 
    // Сравниваем элементы и добавляем меньший в результат
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
 
    // Добавляем оставшиеся элементы
    current.next = l1 || l2;
 
    return dummy.next;
}

Решение 2 (Divide and Conquer)

// Временная сложность: O(N × log k), где k - количество списков, N - общее количество узлов
// Пространственная сложность: O(log k) - глубина рекурсии
 
var mergeKLists_DivideConquer = function(lists) {
    // Базовый случай: пустой массив
    if (!lists || lists.length === 0) return null;
 
    // Вызываем рекурсивное слияние для всего диапазона
    return mergeLists(lists, 0, lists.length - 1);
};
 
// Рекурсивная функция для слияния списков в диапазоне [left, right]
function mergeLists(lists, left, right) {
    // Базовый случай: один список - возвращаем его
    if (left === right) return lists[left];
 
    // Базовый случай: пересечение границ
    if (left > right) return null;
 
    // Находим середину диапазона
    const mid = left + Math.floor((right - left) / 2);
 
    // Рекурсивно сливаем левую половину
    const leftList = mergeLists(lists, left, mid);
 
    // Рекурсивно сливаем правую половину
    const rightList = mergeLists(lists, mid + 1, right);
 
    // Сливаем две половины вместе
    return mergeTwoLists(leftList, rightList);
}
 
// Вспомогательная функция: слияние двух отсортированных списков
// Временная сложность: O(n + m), где n и m - длины списков
function mergeTwoLists(l1, l2) {
    // Dummy node упрощает работу с головой списка
    const dummy = new ListNode(0);
    let current = dummy;
 
    // Сравниваем элементы и добавляем меньший в результат
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
 
    // Добавляем оставшиеся элементы
    current.next = l1 || l2;
 
    return dummy.next;
}

Решение 3 (MinHeap / Priority queue)

: )