从 O(n) 时间和 O(1) 空间中的循环链表中删除重复项

Question

>假设有一个有n个节点的循环单链表。给定一个指向头部的指针，如何删除在 O(n) 时间和 O(1) 空间中包含重复数据的节点？面试官特别要求不要使用哈希表，只使用指针。

Answer 1

从循环链表中删除重复项的快速可能方法是在 O(n log(n)) 中。这是通过对它们进行排序，然后使用以下算法删除重复项。我们知道任何重复项现在都彼此相邻，这就是为什么我们在遍历时删除的原因，所以我们只移动 n 次。

removeDuplicatesOf(node, head)
if(node == node.next || node.next == head)
return
else if(node.value == node.next.value)
node.next = node.next.next
removeDuplicatesOf(node, head)
else
removeDuplicatesOf(node.next, head)

在最坏的情况下，这将以 O(n) 运行，删除排序列表中的所有重复项。由于这两个参数是单数的，因此空间复杂度为 O(1)。这里的问题是您需要对数据进行排序。

由于只允许使用指针，因此将节点想象为指针本身，node.next 是指向下一个节点的指针。我更喜欢对象符号，因为它的可读性更好。

所有其他方法将导致相同或更高的时间复杂度。所提出的想法的问题在于，如果不回头看，就无法比较数据。这个额外的步骤使得复杂度不可能低于 O(n log(n))。唯一的例外是，如果您的列表是预置的。

如果这是面试中的问题，那么以下两种选择之一可能适用：

1)雇主需要一个更了解时间复杂度的新面试官。

2)这是一个测试你对时间复杂度的理解的技巧问题。在这种情况下，答案是不可能的。

后者的可能性要大得多。