Слияние и перестройка связного списка

O(n + m)

Собери новый список, сшивая узлы из двух (или более) списков по порядку, используя фиктивный головной узел (dummy head), чтобы не обрабатывать первую вставку отдельным случаем, затем продвигай тот исходный список, у которого сейчас меньший узел.

Сигналы

слить два отсортированных связных спискаслить k отсортированных списковперестроить список (чередовать переднюю и заднюю половины)переставить узлы без копирования значений в массивфиктивный головной узел / sentinel

Шаблон

function mergeTwoLists(a, b) {
    const dummy = { next: null };
    let tail = dummy;
    while (a && b) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = a || b;
    return dummy.next;
}

Похоже, но не то

Быстрая сортировка сравнением (сортировка слиянием): Шаг слияния в сортировке слиянием сравнивает и объединяет два среза массива по индексам. Слияние списков переиспользует ту же идею «сравни наименьшее, продвинь одну сторону», но сшивает существующие узлы, перепрошивая .next через фиктивный головной узел; массива для деления или индексации здесь нет.

n + m узлов суммарно по спискам -> O(n + m): каждый узел посещается и сшивается ровно один раз.

Изучить этот паттерн