将链表拆分为2个包含最小和最大数字的偶数列表

Question

给定一个按随机顺序排列的整数列表,将其拆分为两个新的链表,这样每个列表元素总和的差异最大,列表长度相差不超过1(在原始情况下) list有奇数个元素). 我不能假设列表中的数字是唯一的.

我想到的算法是在原始链表(O(n·log n)时间,O(n)空间)上进行合并排序,然后使用递归函数走到列表末尾以确定其长度,在递归函数展开时进行拆分.递归函数是O(n)时间和O(n)空间.

这是最佳解决方案吗？如果有人认为它是相关的,我可以发布我的代码.

Answer 1

不，这不是最佳的；您可以在O(n)中找到列表的中位数，然后将其中一半放入一个列表中（小于中位数或等于，最大列表大小为 n/2）并将其中一半放入另一个列表中（(n+1) /2）。它们的总和差异最大化，并且不需要排序（O(n·log(n) ）。所有事情都将在O(n) （空间和时间）内完成。