list - 如何删除具有 O(n) 时间和 O(1) 空间的单链表上的重复元素？

Question

如何删除具有 O(n) 时间和 O(1) 空间的单链表上的重复元素？

元素可以是任何字符、数字，并且它们没有排序。

例如，给定 8 --> 6 --> 7 --> 6 --> 5

返回 8 --> 6 --> 7 --> 5

O(1) 空间似乎很难？

Answer 1

你不能因为你不能在复杂度小于 O(logn) 的列表中搜索......我们必须在删除之前搜索重复项不是吗？然后对于每个元素，你必须做同样的事情，所以它将是 O(nlogn)。这个列表有什么特殊之处，那么可以使用替代逻辑。指定有没有？

Answer 2

有几种不同的方法可以做到这一点：

1. 遍历链表并建立一个哈希表来存储数据及其频率。在遍历的过程中，如果遇到频率值 > 1，可以从列表中移除对应的节点。由于使用了哈希表，这将给出 O(n) 时间但 O(n) 空间。

2. 解决方案 1 中降低 O(n) 空间复杂度的一种方法是：如果您知道输入元素的范围，则可以使用固定大小的数组而不是哈希表。这将使其成为 O(n) 时间和 O(1) 空间。

3. 这是通过重复遍历链表但不使用任何额外内存的方式在时间上包含 o(n2) 可以实现的。

由于假设输入数组未排序，因此如果没有额外的内存，就无法做到这一点。