重复未排序的链表

Question

我发现这个函数可以删除链表中的重复值：

 public static void deleteDups (LinkedListNode n){
  Hashtable table = new Hashtable();
 LinkedListNode previous = null;
 while(n!=null){
  if(table.containsKey(n.data)){
      previous.next = n.next;
  } else {
      table.put(n.data, true);
      previous = n;
  }
  n = n.next;
}
}

为什么最好将元素复制到哈希表中，而不是复制到另一个结构（如不同的链表）中？谢谢

Answer 1

因为检查项目是否存在是链接列表中的O(N)操作，但是对于哈希表O(1)。性能是原因。

if(table.containsKey(n.data))

这是检查当前项目（如果之前看到过（重复项）的地方，并且通过链接列表实现该操作时成本高昂。