Divide the linked list into 2 even lists containing the smallest and largest numbers

Question

Given a linked list of integers in random order, divide it into two new linked lists so that the difference in the sum of the elements of each list is maximum and the length of the lists differs by no more than 1 (in the case that the original list contains an odd number of elements). I cannot assume that the numbers on the list are unique.

The algorithm that I was thinking about was to sort the merge in the original linked list (time O (n · log n), O (n)), and then use the recursive function to go to the end of the list to determine its length while doing the splitting while the recursive function is unwound. A recursive function is O (n) time and O (n) space.

Is this the best solution? I can post my code if someone considers it appropriate.

Answer 1

No, this is not optimal; you can find the median of the list in O (n) , then put half of them in one list (less than the median or equal, the size will be n / 2 before the list) and half of them in another list ((n + 1) / 2). Their difference in sums is maximized, and there is no need to sort (O (n · log (n)). Everything will be done in O (n) (space and time).

Answer 2

? . . O (n).

, O (n) O (1) : , 2 , 1 . .