在链接列表中查找重复值（简单转换成困难）

Question

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

资源

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

BONUS

删除元素，如果你可以遍历它只有一次，

的时间应该是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; 
    } 

} 

运行