import java.util.*;
/*
* Remove duplicates from an unsorted linked list
*/
public class LinkedListNode {
public int data;
public LinkedListNode next;
public LinkedListNode(int data) {
this.data = data;
}
}
public class Task {
public static void deleteDups(LinkedListNode head){
Hashtable<Integer, Boolean> table=new Hashtable<Integer, Boolean>();
LinkedListNode previous=null;
//nth node is not null
while(head!=null){
//have duplicate
if(table.containsKey(head.data)){
//skip duplicate
previous.next=head.next;
}else{
//put the element into hashtable
table.put(head.data,true);
//move to the next element
previous=head;
}
//iterate
head=head.next;
}
}
public static void main (String args[]){
LinkedList<Integer> list=new LinkedList<Integer>();
list.addLast(1);
list.addLast(2);
list.addLast(3);
list.addLast(3);
list.addLast(3);
list.addLast(4);
list.addLast(4);
System.out.println(list);
LinkedListNode head=new LinkedListNode(list.getFirst());
Task.deleteDups(head);
System.out.println(list);
}
}
结果:[1, 2, 3, 3, 3, 4, 4] [1, 2, 3, 3, 3, 4, 4]
它不会消除重复项。
为什么这个方法不起作用?
最佳答案
遍历链表, 将每个元素添加到哈希表中。当我们发现重复元素时,我们删除该元素并继续迭代。因为我们使用的是链表,所以我们可以一次完成所有这些。
下面的解需要O(n)的时间,n是链表中元素的个数。
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;
}
}
关于java - 从未排序的链表中删除重复项,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17643790/