Слияние связных списков

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

Пусть два односвязных списка уже отсортированы по возрастанию. Чтобы получить одну отсортированную цепочку, не нужно складывать все значения в массив и сортировать заново. Достаточно смотреть на текущие первые узлы обеих ещё не обработанных частей и выбирать меньший.

Один проход по двум спискам

Node dummy = new Node(0);
Node tail = dummy;

while (first != null && second != null) {
    if (first.value <= second.value) {
        tail.next = first;
        first = first.next;
    } else {
        tail.next = second;
        second = second.next;
    }

    tail = tail.next;
}

tail.next = first != null ? first : second;
Node merged = dummy.next;

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

Зачем нужен dummy-узел

Временный dummy убирает отдельный случай для первого добавленного элемента: у результата с самого начала есть узел, к которому можно присоединять выбранные элементы через tail.next. Настоящая голова результата находится в dummy.next.

Если в первом списке n узлов, а во втором m, каждый исходный узел обрабатывается не более одного раза. Поэтому время работы — O(n + m). Алгоритм переиспользует существующие узлы и, кроме служебного dummy, не создаёт копий элементов.