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

Linked list merge & reorder

O(n + m)

Стройте ответ на фиктивном узле и берите головы из обоих списков. Фиктивный узел убирает разбор случая пустого результата.

Elman HuseynovОбновлено 17 окт. 2026 г.

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

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

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

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

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

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

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

Источники: Wikipedia (англ.): Merge algorithm

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

Слияние двух отсортированных связных списков

mergeTwoLists(1 → 4 → 5, 2 → 4 → 6 → 8)

список a

список b

уже слито

Сливаем два отсортированных списка в один отсортированный. Результат начинается с фиктивного узла dummy, tail указывает на него.

1 / 13

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

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

interface ListNode {
    val: number;
    next: ListNode | null;
}

function mergeTwoLists(a: ListNode | null, b: ListNode | null): ListNode | null {
    const dummy: ListNode = { val: 0, 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;
}

def merge_two_lists(a, b):
    dummy = Node(0)
    tail = dummy
    while a and 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 or b
    return dummy.next

function mergeTwoLists(?Node $a, ?Node $b): ?Node {
    $dummy = new Node(0);
    $tail = $dummy;
    while ($a !== null && $b !== null) {
        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;
}

    public static ListNode mergeTwoLists(ListNode a, ListNode b) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) { tail.next = a; a = a.next; }
            else { tail.next = b; b = b.next; }
            tail = tail.next;
        }
        tail.next = a != null ? a : b;
        return dummy.next;
    }

    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static ListNode MergeTwoLists(ListNode a, ListNode b) {
        var dummy = new ListNode();
        var tail = dummy;
        while (a != null && b != null) {
            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;
    }

    public class ListNode {
        public int val;
        public ListNode 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 отсортированных списков» или «перестроить список (чередовать переднюю и заднюю половины)». Решение на нём обычно укладывается в O(n + m).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «Слияние и перестройка связного списка» чаще всего путают с этими паттернами: Разворот связного списка, Бинарная куча / очередь с приоритетом, Быстрая сортировка (merge / quick) и Быстрый и медленный указатели.

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

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

Работают без фиктивного узла
Тогда первой дописи нужен отдельный случай для пустого результата. Фиктивный узел убирает эту ветку.
Теряют остаток
Когда один список кончился, во втором ещё есть узлы. Прицепите весь остаток одним шагом.
Создают новые узлы
Такие задачи ждут перевязки исходных узлов. Копирование удваивает память впустую.
Оставляют цикл
Разрезать список значит выставить какой-то next в null. Без этого список зацикливается.

Паттерн «Слияние и перестройка связного списка» решает такие задачи с собеседований: Слияние двух отсортированных списков, Слияние k отсортированных списков, Сортировка связного списка, Перестройка списка, Сложение двух чисел, Разбиение списка и Пересечение двух связных списков.

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