在链表中查找重复值(简单转换为困难)

Question

这似乎是一个非常简单的问题。面试官要求我在链表中找到重复的元素，然后他告诉我一些使问题变得困难的限制。约束是您只需遍历链表一次。

资源

我唯一可用的资源是另一个链表。

奖金

如果只能遍历一次，请删除该元素，

时间应为 O(N)

Q1：我找不到答案，我不知道解决方案是否存在，或者他只是让我感到困惑......如果是，这怎么可能？

Answer 1

你可以使用HashMap，如果要在Java中实现我们可以Map数据结构 映射存储键值对，元素几乎可以O(1)访问，因此此代码段运行O(n)

private void removeDuplicates(final Node node) {
Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
Node n = node;
Node prev = null;
while (n != null) {
if (map.get(n.data) == null) {
map.put(n.data, true);
}
else {
System.out.println("Found Duplicate of: "+n.data);
/*To remove duplicates. do this
if (n.next != null) {
n.data = n.next.data;
n.next = n.next.next;
continue;
}
if (prev != null) {
prev.next = n.next;
}
*/
}
prev = n;
n = n.next;
} 
}