题解 | #删除链表中重复的结点#

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) {
        HashMap<Integer, ListNode> map = new HashMap<>();
        Deque<ListNode> listNodeDeque = new LinkedList<>();

        //遍历链表
        while (pHead != null) {
            if (map.containsKey(pHead.val)) {
                //有重复，删除重复
                ListNode listNode = map.get(pHead.val);
                listNodeDeque.remove(listNode);
            } else {
                //没有重复，往集合里添加
                listNodeDeque.add(pHead);
                map.put(pHead.val, pHead);
            }
		    //遍历向前移动
            pHead = pHead.next;
        }

        //最后，遍历listNodeDeque，组装成一个新的链表
        ListNode newHead = listNodeDeque.poll();
        ListNode tempHead = newHead;
        while (newHead != null) {
            newHead.next = listNodeDeque.poll();
            newHead = newHead.next;
        }
        return tempHead;
    }
}