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

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

Заведите фиктивный узел, который пока никуда не ведёт. Его next и станет настоящей головой.

Держите указатель хвоста, начиная с фиктивного узла. Все узлы дописываются туда.

Сравните головные узлы обоих списков. Допишите меньший и сдвиньте этот список вперёд.

Передвиньте хвост на только что дописанный узел. Повторяйте, пока один список не кончится.

Допишите остаток второго списка целиком. Он уже отсортирован, сравнивать нечего.

В конце верните dummy.next. Ни один узел не копировался, только перевязывался.

1. dummy, a = 1, b = 2Сливаем [1, 4] и [2, 3]. Фиктивный узел пока пуст.
2. хвост = 1, a = 4, b = 21 меньше 2, поэтому дописывается первой.
3. хвост = 2, b = 3Теперь 4 против 2. Следующей идёт двойка.
4. хвост = 3, b = nullТройка тоже обходит четвёрку. Второй список опустел.
5. 1, 2, 3, 4Остаток первого списка дописывается одним шагом.

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;
}

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

Перестроить список с двух концов

Переставьте список в порядке первый, последний, второй, предпоследний и так далее.

Узлы надо перевязать. Копировать значения в массив нельзя.

Найдите середину медленным и быстрым указателем, потом разрежьте список там.

Разверните заднюю половину. Сплетите две половины по одному узлу.

function reorderList(head) {
    if (!head || !head.next) return head;

    let slow = head;
    let fast = head;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    let second = slow.next;
    slow.next = null; // cut the list in two, or the weave loops forever

    let prev = null;
    while (second) {
        const next = second.next;
        second.next = prev;
        prev = second;
        second = next;
    }

    let first = head;
    while (prev) {
        const a = first.next;
        const b = prev.next;
        first.next = prev;
        prev.next = a;
        first = a;
        prev = b;
    }

    return head;
}

Слияние и перестройка связного списка: когда применять?

Эти формулировки в условии ведут сюда:

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

Слияние и перестройка связного списка: с чем путают?

• Разворот связного списка (Linked list reversal): Разворот меняет ссылки внутри одного списка. Слияние перевязывает узлы между двумя списками.
• Бинарная куча / очередь с приоритетом (Binary heap / priority queue): При k списках куча выбирает наименьшую голову за log k. Для двух списков хватает одного сравнения.
• Быстрая сортировка (merge / quick) (Fast sort (merge / quick)): Шаг слияния в merge sort это ровно этот цикл. Здесь списки приходят уже отсортированными.
• Быстрый и медленный указатели (Fast & slow pointers): Перестройка начинается с поиска середины, а это тот приём. Сплетение после него это уже этот.

Слияние и перестройка связного списка: частые ошибки

• Работают без фиктивного узла

  Тогда первой дописи нужен отдельный случай для пустого результата. Фиктивный узел убирает эту ветку.

• Теряют остаток

  Когда один список кончился, во втором ещё есть узлы. Прицепите весь остаток одним шагом.

• Создают новые узлы

  Такие задачи ждут перевязки исходных узлов. Копирование удваивает память впустую.

• Оставляют цикл

  Разрезать список значит выставить какой-то next в null. Без этого список зацикливается.

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

• Слияние двух отсортированных списков: Чистая форма: фиктивный узел и одно сравнение на узел.
• Слияние k отсортированных списков: Куча держит головной узел каждого списка.
• Сортировка связного списка: Разрежьте посередине, отсортируйте половины и слейте.
• Перестройка списка: Разрежьте, разверните заднюю половину и сплетите.
• Сложение двух чисел: Идите по обоим спискам и переносите разряд.
• Разбиение списка: Два фиктивных узла: один для малых значений, другой для остальных.
• Пересечение двух связных списков: Два обходчика, меняющие списки на конце.

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

O(n + m)

n плюс m узлов дают O(n + m) времени и O(1) памяти. Слияние k списков кучей стоит O(N log k).