2

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

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

我完全理解 O(nlog(n)) 比 O(n) 更差（慢）。

但出于好奇 - 用于反转简单链表的 O(nlog(n)) 算法可能是什么？具有恒定额外内存的算法是可取的。

4

6 回答 6

11

我想你很困惑。你说的是 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) 中做到这一点。

于 2009-07-21T09:35:34.423 回答
7

Every O(n) algorithm is also O(n log n), so the answer is yes.

于 2009-07-21T09:44:21.990 回答
1

出色地...

您可以使用接受链表并将其反转的递归，通过使用链表的两半调用自身，如果输入只是两个节点，它将反转它们。

这是非常低效的，但我相信它是 O(nlog(n))...

伪代码中类似于以下内容（假设您有一个len以 O(n) 返回列表长度的函数和一个sub_list(list, start_id, end_id)返回从 start_id 开始并以 O(N) 结束于 end_id 的列表子集的函数）：

function invert(list)

    if len(list) == 1 return list

    if len(list) == 2:
        new_list = list.next
        new_list.next = list
        return new_list

    middle_of_list = len(list) / 2  <-- integer division

    first_half = invert ( sub_list(list, 1, middle_of_list) )
    second_half = invert ( sub_list(list, middle_of_list+2, len(list) )

    first_half.next = second_half

    return first_half
于 2009-07-21T09:42:27.640 回答
1

Stupid idea, but O(n log n) and not O(n)

  • Assign each item of a list an unique ID. The id of each successor should be greater than the id of the item (O(n))
  • Sort the items by ascending order using the id as key using any comparison based sorting algorithm (O(n log n))
  • Build up a new list using the order given by sorting the items (O(n))
于 2009-07-21T09:44:24.173 回答
0

如果你是迂腐的，那么这个算法是 O(n log n)，因为指针的大小至少为 log n，并且必须被分配 n 次。

但实际上机器具有固定的字长，因此通常不会考虑到这一点。

于 2009-07-21T10:35:39.217 回答
0

如果问题实际上是针对 Ω(nlgn) 算法的，也许这个过于复杂的算法可以吗？

  • 从链表构建平衡的树结构
  • 每个叶子都包含来自链表的原始值和链表中值的索引号；使用索引作为树键
  • 遍历树以与原始索引相反的顺序报告所有叶子
  • 从匹配的值创建一个新的链表
于 2009-07-21T13:16:59.597 回答