Где применяется
1. Задача
Два сервиса присылают тебе по ленте событий. Каждая лента уже упорядочена по времени события. Тому, кто читает ленту, нужна одна общая лента, тоже по порядку. То есть на входе две отсортированные цепочки, а на выходе нужна одна отсортированная.
Самый прямой способ: сложить обе в массив, склеить и отсортировать. Это работает, но не пользуется тем, что каждый вход уже отсортирован. Ты платишь за полную сортировку, которая здесь не нужна, и ещё за память под новый массив.
Обе цепочки уже упорядочены, поэтому их можно сплести, глядя только на два первых узла. Берёшь меньший, переходишь к следующему узлу в той цепочке, откуда взял, и повторяешь. Один проход, без новой сортировки и без нового списка.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитmergeTwoLists(1 → 4 → 5, 2 → 4 → 6 → 8)Сливаем два отсортированных списка в один отсортированный. Результат начинается с фиктивного узла dummy, tail указывает на него.
Как узнать
Эти слова в условии значат этот паттерн
- слить два отсортированных связных списка
- слить k отсортированных списков
- перестроить список (чередовать переднюю и заднюю половины)
- переставить узлы без копирования значений в массив
- фиктивный головной узел / sentinel
Похоже, но не то
- Разворот связного списка (Linked list reversal)
Разворот меняет ссылки внутри одного списка. Слияние перевязывает узлы между двумя списками.
- Бинарная куча / очередь с приоритетом (Binary heap / priority queue)
При k списках куча выбирает наименьшую голову за log k. Для двух списков хватает одного сравнения.
- Быстрая сортировка (merge / quick) (Fast sort (merge / quick))
Шаг слияния в merge sort это ровно этот цикл. Здесь списки приходят уже отсортированными.
- Быстрый и медленный указатели (Fast & slow pointers)
Перестройка начинается с поиска середины, а это тот приём. Сплетение после него это уже этот.
n плюс m узлов дают O(n + m) времени и O(1) памяти. Слияние k списков кучей стоит O(N log k).
На LeetCode
Задачи, где нужно слить отсортированные связные списки, отсортировать связный список или переставить его узлы, разрезав пополам и сплетя половины. Слияние делают фиктивная голова и одно сравнение на узел.
Это задача урока, с той же фиктивной головой.
Найди середину (урок 47), разверни вторую половину (урок 46) и сплети половины по одному узлу.
Сортировка слиянием по узлам, с разрезом по середине и слиянием функцией из урока.
Сливай списки парами, затем пары результатов, пока не останется один список.