import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        //思路：遍历链表，将节点值放入List中，并且每次放入时，判断这个值是否存在
        //如果已经存在list中，证明这个词存在了至少两次。标记位重复值。
        // 将这个存在的值放入set中
        ListNode res = new ListNode(0);
        res.next = new ListNode(0);
        //set只用来放重复的数值
        Set<Integer> set = new HashSet<>();
        //list用来存放所有的值，但同样的值只会出现一次
        //例如给出的例子中，最终list是1,2,3,4,5
        List<Integer> list = new ArrayList<>();
        //先取出每个节点的val值
        while( pHead != null && pHead.next!=null){
        if(!list.contains(pHead.val)){
            list.add(pHead.val);
        }else{
            set.add(pHead.val);
        }
         pHead = pHead.next;
        }
        
        //第二阶段.只存放没有重复的值。这个真的是无解啊！
       //我已经有了一个list={1,2,3,4,5}，只是想把它一个个的放入ListNode中，
       //形成 1>2>3>4>5。怎么就想不通怎么放
        for(int i = 0; i < list.size(); i++){
            if(!set.contains(list.get(i))){
                res.next.val = list.get(i);
                res = res.next ;
            }
            
        }
        return res.next;
    }
}