题目源自CC150一书，原题为给定未排序的结点，要求输出删去重复结点的单链表。
书中介绍的两种方法及实现：
1.哈希表记录已有节点元素，去重 时间复杂度O（N）开辟新空间 哈希set集合记录
2.双重循环，定哨兵扫描链表，去重 时间复杂度O(N^2) 不需开辟新空间
Java代码实现：
import java.util.HashSet;
public class Main {
public static void main(String[] args) {
int[] arr = {1,5,4,6,2,6,2};
//arr = new int[]{1,6,7,3,6};
Node head = new Node(0);//哑元
Node p = head;
for (int i = 0; i < arr.length; i++) {//数组转链表
p.next = new Node(arr[i]);
p = p.next;
}
//removeRepeation(head);
removeRepeation2(head);
//链表节点的顺序遍历
Node p_ = head.next;
while(p_ != null) {
System.out.print(p_.value + " ");
p_ = p_.next;
}
}
private static void removeRepeation2(Node head) {
Node pivoat = head.next;
Node pre = head;
while(pivoat != null) {
Node p = pivoat.next;
while(p != null) {
if(p.value == pivoat.value)//重复节点，删除
pre.next = p.next;
else
pre = p;//每次保留前一个节点
p = p.next;
}
//每趟结束后重新更新pre指针,保持pre指针从哨兵开始否则会重复删除
pivoat = pivoat.next;
pre = pivoat;
}
}
private static void removeRepeation(Node head) {
HashSet<Integer> set = new HashSet<Integer>();//set集合做重复记录
Node p = head.next;
Node pre = head;//保留前一个节点，为删除当前节点使用
while(p != null) {
if(set.contains(p.value)) {//如果有删除当前节点
pre.next = p.next;
}else {
set.add(p.value);
pre = p;//注意如果删除了当前节点，需要保持pre指针指向删除节点的上一个位置
}
p = p.next;
}
}
private static class Node{
int value;
Node next;
public Node(int value) {
super();
this.value = value;
}
}
}
