[数据结构与算法]leetcode 82. Remove Duplicates from Sorted List II (排序链表中删除重复数字II）

删除排好序的单向链表中重复的数字。
注意是把重复的数字都删掉，而不是unique。

思路：
链表已经是排好序的，这就说明相同的数字都是在一起的。

假设[1, 2, 2, 2, 3]
删除2的时候需要确定它的左边界和右边界，分别是index=1和index=3
同时，因为是单向链表，需要知道左边界左边的一个node，
假设左边界是left, 右边界是right, left的前一个node是pre
那么删除如下：
pre.next = right.next;
right.next = null;
right = pre.next;

如何确定左右边界，让它们每次向右走一步，当出现right.val == left.val时，只移动right，直到不再满足。

同时还需要一个flag，记录是否需要删除，不删除的话只需要遍历即可。

但是还有一个问题，如果是[1, 1]怎么办，没有head的前一个节点了。
需要新定义一个ListNode充当newHead, newHead.next = head，最后返回newHead.next即可。

    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return head;
        
        ListNode newHead = new ListNode(101);
        newHead.next = head;
        ListNode pre = newHead;
        ListNode left = newHead;
        ListNode right = newHead.next;
        boolean delete = false;
        
        while(right != null) {
            delete = false;
            while(right != null && right.val == left.val) {
                left.next = right.next;
                right.next = null;
                right = left.next;
                delete = true;
            }
            if(delete) {
                pre.next = right;
                left.next = null;
                left = pre;
            }
            pre = left;
            left = right;
            if(right != null) right = right.next;
        }
        return newHead.next;
    }

如果不想用这么多的指针，可以利用原有的head指针，每次比较head.next.val 和 head.val 即可
head就相当于上面的右边界right指针，其实只需要右边界就足够。
这样就不需要再定义left, right指针了。

    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return head;
        
        ListNode newHead = new ListNode(101);
        ListNode pre = newHead;
        newHead.next = head;
        boolean delete = false;
        
        while(head != null && head.next != null) {
            delete = false;
            while(head.next != null && head.val == head.next.val) {
                delete = true;
                head = head.next;
            }
            if(delete) {
                pre.next = head.next;
                head.next = null;
                head = pre.next;
            }else {
                pre = head;
                head = head.next;
            }
        }
        
        
        
        return newHead.next;
    }