82.删除排序链表中的重复元素 II.md

82 删除排序链表中的重复元素 II

题目：
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3

思路：
在迭代过程中，如果cur.next.val == cur.next.next.val说明此时有重复元素，此时创建一个临时指针temp，指向cur的下一个节点，即temp指向的第一个重复元素所在的位置。通过while循环去重，去重后，temp指向的是重复元素中的最后一个位置。最后cur.next = temp.next就实现了消除重复元素。
当然，如果未发现重复元素，则直接向后迭代即可。

代码：

public ListNode deleteDuplicates(ListNode head) {
    //为了防止删除的是头节点，新建一个节点dummy，在头节点之前
    //cur从dummy开始遍历
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode cur = dummy;
    while(cur.next != null && cur.next.next != null){
        //当cur之后开始重复时，新建一个节点temp指向重复的第一个节点
        if(cur.next.val == cur.next.next.val){
            ListNode temp = cur.next;
            //然后temp不断移动到该重复的最后一个节点
            while(temp.next != null && temp.val == temp.next.val)
                temp = temp.next;
            //temp标记着重复的最后一个节点。让cur的下一个节点指向它之后，即跳过了所有重复节点
            cur.next = temp.next;
        }
        //如果cur之后不遇到重复节点，则cur正常向后移动
        else
            cur = cur.next;
    }
    return dummy.next;
}

总结：
对于此类链表题目，为了防止删除头节点的极端情况的产生。设置一个空结点dummy，使dummy指向传入的head头节点。cur遍历链表从dummy结点开始。最后函数返回dummy.next即head。