---
title: "Слияние и перестройка связного списка"
url: https://algopath.pro/ru/patterns/linked-list-merge
language: ru
summary: "Стройте ответ на фиктивном узле и берите головы из обоих списков. Фиктивный узел убирает разбор случая пустого результата."
updated: 2026-08-24
---

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

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

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

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

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

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

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

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

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

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

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

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

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

- **Разворот связного списка** - Разворот меняет ссылки внутри одного списка. Слияние перевязывает узлы между двумя списками.
- **Бинарная куча / очередь с приоритетом** - При k списках куча выбирает наименьшую голову за log k. Для двух списков хватает одного сравнения.
- **Быстрая сортировка (merge / quick)** - Шаг слияния в merge sort это ровно этот цикл. Здесь списки приходят уже отсортированными.
- **Быстрый и медленный указатели** - Перестройка начинается с поиска середины, а это тот приём. Сплетение после него это уже этот.

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

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

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

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

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

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

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

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

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

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

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

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

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

## JavaScript

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

## Python

```python
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
```

## PHP

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