[JAVA]从链表中删除重复数据（时间、空间）

一、从链表中删除重复数据

1）方法一（空间换取时间）

1、思路：利用hashmap来存储数据，当在hashmap中存在跳过这个数据，当不存在时，将这个数加入hashmap中

其事件复杂度是O(n),但是付出了空间复杂度

2、代码：

public void delDuplicateNum(LinkList list) { HashMap<Integer,Integer> map=new HashMap<Integer,Integer>(); LinkList list1=list; LinkList pre=null; while(list1!=null) { if(map.containsKey(list1.nodeValue)) pre.next=list1.next; else { map.put(list1.nodeValue, 1); pre=list1; } list1=list1.next; } while(list!=null) { list=list.next; } } 2）方法二（时间换取空间）

1、思路：

利用双循环来实现删除重复数据

其时间复杂度是O（n^2）,空间复杂度是O(1)

2、代码

public void delDup(LinkList list) { LinkList list1=list; LinkList tmp=null; while(list1!=null) { tmp=list1; while(tmp!=null) { if(tmp.next!=null&&list1.nodeValue==tmp.next.nodeValue) { tmp.next = tmp.next.next; } else tmp=tmp.next; } list1=list1.next; } }