描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5

注：

1. 首节点是重复节点的情况
2. 3, 3, 4, 5, 5，注意中间有个节点不能被跳过
3. 3, 3, 4, 4，不能直接判断当前节点和下一个节点是否相等，否则会出现2->4的情况

思路1：使用Set存储重复节点

使用Set存储重复节点，再次遍历的时候删除重复节点

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        Set<Integer> set = new HashSet<>(); 
        ListNode cur = pHead;
        while(cur != null) {
            if(cur.next != null && cur.val == cur.next.val) {
                set.add(cur.val);
            }
            cur = cur.next;
        }
        //设置哨兵节点，防止首节点是重复节点
        ListNode newNode = new ListNode(-1);
        newNode.next = pHead;
        ListNode pre = newNode;
        cur = pHead;
        while(cur != null) {
            if(set.contains(cur.val)) {
                //跳过重复的节点
                pre.next = pre.next.next;
                cur = cur.next;
            } else {
                pre = pre.next;
                cur = cur.next;
            }
        }
        return newNode.next;
    }
}

思路2

保存重复节点的前一个节点（如节点2），遍历直到节点不重复，2指向5。

public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        //设置哨兵节点
        ListNode newNode = new ListNode(0);
        newNode.next = pHead;
        ListNode pre = newNode;
        ListNode cur = pHead;
        while(cur != null) {
            if(cur.next != null && cur.val == cur.next.val) {
                while(cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                cur = cur.next;
                //这里暂时不移动pre，而是修改next节点
                //如果有连续重复的数字，会再次修改next节点
                pre.next = cur;
            } else {
                //节点不相同，同时前进
                pre = cur;
                cur = cur.next;
            }
        }
        return newNode.next;
    }
}