algorithm - 是否有用于反转单链表的 O(n log(n)) 算法？

Question

在对 this answer 的评论中提出了一个想法，即反转一个简单的链表只能在 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) 中完成。