Узлы, dummy и безопасное перенаправление ссылок

Трассировка 1→4 и 2→3: dummy начинает результат, tail последовательно принимает 1, 2, 3, 4; настоящая голова ответа находится в dummy.next.

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

Узел односвязного списка содержит значение и ссылку next на следующий узел. head указывает на первый узел, а последняя ссылка равна null/None. Узлы могут находиться в разных местах памяти: позиция элемента определяется цепочкой ссылок, а не формулой адреса по индексу.

В двусвязном списке узел дополнительно хранит prev. Это упрощает движение назад и удаление известного узла, но требует больше памяти и более аккуратного обновления двух направлений. Ссылка tail даёт быстрый доступ к концу, однако сама по себе не делает поиск предшественника быстрым в односвязной модели.

Какие операции действительно O(1)

Если уже известен адрес узла и нужные соседние ссылки, вставка после него меняет постоянное число стрелок и занимает O(1). Удаление следующего узла в односвязном списке тоже O(1). Но сначала найти узел по значению или позиции обычно нужно проходом от head, то есть за O(n).

Поэтому фраза «вставка в связный список O(1)» неполна: она предполагает, что место вставки уже найдено. Случайный доступ list[i] у такой структуры невозможен за O(1).

Что платим за локальное перенаправление

Каждый узел хранит служебные ссылки, а переход node = node.next зависит от предыдущего чтения памяти. Это хуже использует кэш процессора, чем плотный проход по массиву. Во многих прикладных задачах динамический массив оказывается проще и быстрее, даже если отдельная вставка теоретически требует сдвига.

Связные списки остаются популярны на собеседованиях, потому что компактно проверяют работу со ссылками, инвариантами границы и владением: потерянный next, неверно обновлённая голова или случайный цикл сразу показывают качество рассуждения.

В стандартном C++ std::list — двусвязная структура, но интервью-задачи чаще дают собственный Node*. Python list не является связным списком; узловую модель для учебной задачи описывают отдельным классом Node.

Sentinel убирает не данные, а ветвление

Dummy/sentinel — служебный узел перед настоящей головой. Он позволяет одинаково обрабатывать вставку первого и последующих узлов: алгоритм всегда меняет tail.next, а в конце возвращает dummy.next. Sentinel не обязан входить в логические данные результата.

Как слить два отсортированных связных списка?

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

Копирование значений и построение нового списка

Скопировать оба списка в массив, отсортировать значения и построить третий список.

Что теряется при пересоздании всех узлов?

Копирование тратит O(n+m) дополнительной памяти, теряет идентичность узлов и делает лишнюю сортировку O((n+m) log(n+m)).

Меньшая из двух голов — следующий узел результата

Головы обоих списков — минимальные оставшиеся элементы. Dummy-узел даёт стабильную точку перед головой ответа, поэтому первая вставка не требует отдельной ветви.

Что гарантируют dummy и tail?

dummy.next начинает отсортированный результат, tail указывает на его последний узел, а first и second начинают два ещё не слитых суффикса.

Перенаправляем next и один раз присоединяем остаток

Пока оба списка непусты, присоединять к tail.next меньшую голову, продвигать выбранный список и затем tail. После цикла одним присваиванием присоединить оставшийся суффикс. Вернуть dummy.next.

Слияние списков на C++17 и Python 3

C++17

#include <cassert>
#include <vector>
using namespace std;

struct Node {
    int value;
    Node* next;
};

Node* mergeSorted(Node* first, Node* second) {
    // Preconditions: both lists are acyclic and node-disjoint.
    Node dummy{0, nullptr};
    Node* tail = &dummy;
    while (first != nullptr && second != nullptr) {
        if (first->value <= second->value) {
            tail->next = first;
            first = first->next;
        } else {
            tail->next = second;
            second = second->next;
        }
        tail = tail->next;
    }
    tail->next = first != nullptr ? first : second;
    return dummy.next;
}

int main() {
    Node four{4, nullptr};
    Node one{1, &four};
    Node three{3, nullptr};
    Node two{2, &three};
    Node* merged = mergeSorted(&one, &two);
    vector<int> values;
    for (Node* node = merged; node != nullptr; node = node->next) values.push_back(node->value);
    assert((values == vector<int>{1, 2, 3, 4}));
    assert(mergeSorted(nullptr, nullptr) == nullptr);
}

Python 3

class Node:
    def __init__(self, value: int, next_node: "Node | None" = None) -> None:
        self.value = value
        self.next = next_node


def merge_sorted(first: Node | None, second: Node | None) -> Node | None:
    """Merge two sorted, acyclic, node-disjoint lists by relinking nodes."""
    dummy = Node(0)
    tail = dummy
    while first is not None and second is not None:
        if first.value <= second.value:
            tail.next = first
            first = first.next
        else:
            tail.next = second
            second = second.next
        tail = tail.next
    tail.next = first if first is not None else second
    return dummy.next


merged = merge_sorted(Node(1, Node(4)), Node(2, Node(3)))
values: list[int] = []
while merged is not None:
    values.append(merged.value)
    merged = merged.next
assert values == [1, 2, 3, 4]
assert merge_sorted(None, None) is None

Линейное время и O(1) вспомогательных ссылок

O(n+m) времени и O(1) дополнительной памяти: каждый исходный узел присоединяется один раз, а dummy — единственный локальный служебный узел.

Память самих входных узлов составляет O(n + m) и не считается дополнительной памятью алгоритма. Формулировка O(1) относится только к нескольким рабочим ссылкам; она не означает, что связный список хранится бесплатно.

Пустые списки, равные ключи и владение узлами

Оба списка пусты; один пуст; равные значения; сильно разные длины. При равенстве выбор первого списка сохраняет стабильный межсписочный порядок. Общий узел или цикл нарушает входной контракт: функция не пытается обнаружить их за O(1) памяти и может зациклиться, поэтому вызывающий код обязан гарантировать раздельное владение и ацикличность.

Тесты на голову, хвост и пустой ввод

null+null -> null, null+[1] -> [1], [1,4]+[2,3] -> [1,2,3,4], равные головы и длинный остаток. Если списки пришли из ненадёжного источника, до вызова отдельно проверяют отсутствие цикла и пересечения адресов; такие структуры не передают в mergeSorted.

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

Нужно наращивать список с головы, а отдельная обработка «первого добавленного узла» начинает усложнять ветвления.

Когда перенаправлять исходные узлы небезопасно?

Если исходные списки должны сохраниться неизменными, понадобятся новые узлы; при неотсортированном входе этот merge некорректен. Для частого доступа по индексу, бинарного поиска, сортировки и плотного последовательного чтения выбирайте массив. Связный список оправдан, когда алгоритм уже располагает нужными узлами и основная работа — локальное перенаправление связей.

Мини-проверка: зачем нужен dummy?

Вопрос: зачем нужен dummy, если он не входит в ответ? Ответ: он всегда существует перед первой настоящей вершиной и убирает особый случай пустого результата.

Мини-проверка: почему остаток можно присоединить целиком?

Вопрос: почему после основного цикла можно присоединить остаток целиком? Ответ: один список уже пуст, а оставшийся суффикс сам отсортирован и не меньше последнего выбранного узла.

Проследите tail для списков 1→4 и 2→3

Для 1→5→7 и 2→3→8 после каждого шага запишите tail, головы двух суффиксов и цепочку от dummy.next.

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

Задача 1

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

Sentinel убирает особый случай первой головы

Dummy даёт постоянную точку перед головой, а tail превращает слияние в одинаковое перенаправление на каждом шаге.