1. 辅助空间

1.1 分析

两次遍历链表。第一次遍历，将重复的值存入set。第二次遍历，如果set中存在，则在链表中删除。

1.2 代码

import java.util.HashSet;
public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead==null) return null;
        //将重复结点存入set
        HashSet<Integer> set = new HashSet<>();
        ListNode pre = pHead;
        ListNode cur = pre.next;
        while(cur!=null){
            if(pre.val == cur.val){
                set.add(cur.val);
            }
            pre = cur;
            cur = cur.next;
        }
        //将重复结点删除
        //先处理头结点
        while(pHead!=null&&set.contains(pHead.val)){
            pHead = pHead.next;
        }
        if(pHead == null){
            return null;
        }
        //再处理后面的重复结点
        pre = pHead;
        cur = pre.next;
        while(cur != null){
            if(set.contains(cur.val)){
                pre.next = cur.next;
                cur = cur.next;
            }
            else{
                pre =cur;
                cur = cur.next;
            }
        }
        return pHead;
    }
}

1.3 复杂度

空间：最坏的情况是存一半结点 ，O(n/2)，最好的情况是一个也不存，O(1)
时间：O(n)

2. 辅助指针

2.1 分析

边遍历便删除。设置一个辅助头结点，避免单独讨论头结点重复的情况。设置两个辅助结点pre和cur，当cur和cur.next相等时，开启子循环，cur一直向前走，直到最后一个重复结点，退出子循环。调整pre、cur继续总体循环。

2.2 代码

public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead==null) return null;
        // 构建辅助头结点
        ListNode head = new ListNode(Integer.MIN_VALUE);
        head.next = pHead;
        ListNode pre = head;
        ListNode cur = head.next;
        while(cur!=null){
            if(cur.next != null && cur.next.val == cur.val){
                // 结点重复，一直前进
                while(cur.next != null && cur.next.val == cur.val){
                    cur = cur.next;
                }
                // 退出循环时，cur 指向重复值， cur.next 指向第一个不重复的值
                // cur 继续前进
                cur = cur.next;
                // pre 连接新结点
                pre.next = cur;
            }else{
                pre = cur;
                cur = cur.next;
            }
        }
        return head.next;
    }
}

2.3 复杂度

空间：O(1)
时间：O(n)