/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/

import java.util.*;
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        
        //初步想想法： 弄一个hashmap 然后进行key存储起来。然后 如果存在的就为1，如果大于1的就想办法进行删除
        //不过注意这个数组是排序的，从这个点入手可以
        
        ListNode res = new ListNode(-1);
        ListNode p=pHead;
        ListNode pre = res;
        while (p != null) {
            // 进入循环时，确保了 pHead 不会与上一节点相同
            if (p.next == null || p.next.val != p.val) {
                pre.next = p;
                pre = p;
            }
            // 如果 pHead 与下一节点相同，跳过相同节点（到达「连续相同一段」的最后一位）
            while (p.next != null && p.val == p.next.val) p = p.next;
            p = p.next;
        }
        pre.next = null;
        return res.next;

    }
}

class Solution {
    public ListNode deleteDuplication(ListNode head) {
        if (head == null) return head;
        ListNode dummy = new ListNode(-109);
        ListNode tail = dummy;
        while (head != null) {
            // 值不相等才追加，确保了相同的节点只有第一个会被添加到答案
            if (tail.val != head.val) {
                tail.next = head;
                tail = tail.next;
            }
            head = head.next;
        }
        tail.next = null;
        return dummy.next;
    }   
}