在链表中查找重复值（简单转化为困难）

Question

这似乎是一个很简单的问题。我曾经被面试官问过要在链表中找到重复的元素，然后他告诉我一些使问题对我来说困难的约束条件。限制条件是你只能遍历链表一次。

资源

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

奖金

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

时间应该是O(N)

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

Answer 1

您可以使用 HashMap，如果要在 Java 中实现，我们可以使用 Map 数据结构 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;
    } 

}

在链表中查找重复值（简单转化为困难）

Find duplicates values in the linked list (Simple convert into difficult)

traversal

linked-list

data-structures