разбить связанный список на 2 четных списка, содержащих самые маленькие и самые большие числа

Question

Учитывая связанный список целых чисел в случайном порядке, разбейте его на два новых связанных списка так, чтобы разница в сумме элементов каждого списка была максимальной, а длина списков отличалась не более чем на 1 (в случаечто исходный список имеет нечетное количество элементов). Я не могу предположить, что числа в списке уникальны.

Я думал, что алгоритм должен был выполнить сортировку слиянием в исходном связанном списке ( O (n ·)запишите n) время, O (n) пробел), а затем используйте рекурсивную функцию, чтобы перейти к концу списка, чтобы определить его длину, выполняя разбиение, пока рекурсивная функция раскручивается.Рекурсивная функция: O (n) время и O (n) пробел.

Является ли это оптимальным решением?Я могу опубликовать свой код, если кто-то считает, что это актуально.

Answer 1

Нет, это не оптимально; Вы можете найти медиану списка в O (n) , затем поместить половину из них в один список (меньше, чем медиана или равно, размер списка будет n / 2) и половина из них в другом списке ((n + 1) / 2). Их разность сумм максимальна, и нет необходимости сортировать ( O (n & middot; log (n) ). Все будет выполнено в O (n) (пространство и время). ).

Answer 2

Зачем вам нужна рекурсивная функция? При сортировке списка вы можете считать его элементами. Тогда просто разделите его пополам. Это уменьшает O (n) пространство.

Даже если вы не можете сосчитать длину списка при сортировке, она все равно может быть разделена на O (n) время и пространство O (1): получить два итератора списка в начале, продвигать первые 2 элемента на каждом шаге, затем 1 элемент на каждый шаг. Когда первый достигает конца списка, второй - вырезать.