是否有用于反转简单链表的O(nlog(n))算法？

Question

在对这个答案的评论中提出了一个想法,即反转简单链接列表只能在O(nlog(n))中完成,而不是在O(n)时间内完成.

这绝对是错误的 - O(n)反转不是问题 - 只需遍历列表并随时更改指针.需要三个临时指针 - 这是不变的额外内存.

我完全理解O(nlog(n))比O(n)更差(更慢).

但出于好奇 - 可能是一个用于反转简单链表的O(nlog(n))算法？具有恒定额外存储器的算法是优选的.

Answer 1

我觉得你很困惑.你说O(n log(n))实际上比O(n)差.你或许是指O(log n)？如果是这样,答案是否定的.您无法在O(log n)中反转链接列表.O(n)是微不足道的(显而易见的解决方案).O(n log(n))没有多大意义.

编辑:好的,所以你的意思是O(n log(n)).然后答案是肯定的.怎么样？简单.您对列表进行排序:

1. 计算列表的长度.费用:O(n);
2. 创建一个相同大小的数组;
3. 以随机顺序将链表的元素复制到数组中,将原始顺序作为元素的一部分.例如:[A,B,C] - > [(B,2),(C,3),(A,1)].费用:O(n);
4. 使用反向原始顺序的有效排序(例如快速排序)对数组进行排序,例如[(C,3),(B,2),(A,1)].成本:O(n log(n));
5. 从反转数组创建链接列表.费用:O(n).

总成本:O(n log(n))

尽管有所有中间步骤,但排序是最昂贵的操作.O(n)个其他步骤是常数(意味着步数不是n的因子),因此总成本是O(n log(n)).

编辑2:我最初没有按随机顺序放置列表项,但意识到你可以争辩说已经排序的列表上的有效排序小于O(n log(n)),即使你正在逆转它.现在我并不完全相信这种情况,但上述修订删除了这种潜在的批评.

是的,这是一个病态问题(和答案).当然你可以在O(n)中完成.

Answer 2

每个O(n)算法也是O(n log n),所以答案是肯定的.