В этой задаче LeetCode нам дали массив элементов LinkedList и попросили вернуть один LinkedList, содержащий все узлы ListNodes, содержащиеся в предоставленных элементах LinkedList, в упорядоченном виде. Другими словами, мы должны объединить все объекты LinkedList вместе, а затем отсортировать их.

Для большинства этих решений мы будем использовать слияние LinkedList на основе рекурсии, которое мы создали для задачи LeetCode 21, Объединить два отсортированных списка.

Решение №1. Объединение всех объектов LinkedList в первый

Это решение, вероятно, самое простое для понимания, но и наименее эффективное. Вооружившись нашей функцией слияния, достаточно просто перебрать все предоставленные элементы LinkedList и объединить их содержимое в первый LinkedList. Функция слияния занимается сортировкой, поэтому у нас остается полностью объединенный, упорядоченный LinkedList.

Проблема с этим решением заключается в эффективности. Поскольку наша операция слияния постоянно выполняется с постоянно растущим первым LinkedList, он с каждым разом становится все больше и больше. Гораздо эффективнее было бы объединить вместе меньшие элементы LinkedList, а затем объединить их выходные данные и т. д. Именно это мы и рассмотрим далее.

Решение № 2: рекурсивное слияние

В этом решении мы передаем рекурсивной функции наш массив объектов LinkedList. Затем эта функция вычисляет среднюю точку и снова вызывает себя как слева, так и посередине, а также справа + 1 и посередине, или, если осталось недостаточно LinkedLists, она просто возвращает то, что ей было дано.

Это означает, что в конечном итоге мы вызываем функцию для каждой пары LinkedList, объединяя их по мере продвижения. Таким образом, к тому времени, когда рекурсивная функция проделает свой путь назад до самого верха, у нас останется один упорядоченный LinkedList.

Для примера предположим, что у нас есть 3 LinkedList. Мы передаем функции эти списки, и она создает 2 пары слияния; 1+2 и 3+ничего. Затем он объединяет 1 с 2 и 3 ни с чем, затем делает шаг назад и объединяет объединенные 1+2 с 3+ничего, давая нам единый упорядоченный LinkedList.

Решение № 3. Преобразование в массив

Я признаю, что этот метод является своего рода обманом, но он работает, и работает быстро. Здесь мы просматриваем каждый предоставленный LinkedList, добавляя их значения в общий массив. Затем мы упорядочиваем этот массив и преобразуем его в новый LinkedList.

Обратите внимание, что способ преобразования массива в LinkedList заключается в том, чтобы сделать это в обратном порядке. Это потому, что это позволяет нам создать последний ListNode, который ни на что не указывает, а затем создать предпоследний ListNode, который указывает на последний, а затем третий-последний ListNode, который указывает на второй -до последнего, а потом... ну вы поняли.