题解 | #删除有序链表中重复的元素-II#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        //创建一个虚拟头节点用于处理第一个元素重复的情况
        ListNode dummy = new ListNode(1001);
        dummy.next = head;
        ListNode last = dummy;
        ListNode mark = dummy.next;
        if(mark == null) return head;
        ListNode cur = mark.next;
        if(cur == null) return head;
        //判断是否已经有前置元素重复
        Boolean isSame = false;
        while(cur!=null){
            if(mark.val != cur.val){
                if(isSame){
                    isSame = false;
                    last.next = cur;
                    mark = cur;
                    cur = cur.next;

                }
                else {
                    last = mark;
                    cur = cur.next;
                    mark = mark.next;
                }
                
            }
            else {
                cur = cur.next;
                isSame = true;
            }
        }
        //处理最后一个元素是重复的情况，即cur == null，但是mark == cur，没有删除最后一部分重复元素
        if(isSame) {
            isSame = false;
            last.next = cur;
        }
        return dummy.next;
    }
}

链表长度为0，1时，直接返回

需要加一个dummy虚拟头节点，处理链表开头的元素是重复元素的情况。

使用三个指针，mark指向需要比较的元素，cur指向当前的元素，last指向当前比较的元素的前一个元素，方便删除链表。

需要一个标志位isSame区分当cur不等于mark时，是否前面已经有重复的元素。

不断移动last，mark，cur。当mark==cur时，last和mark不动，将标志位isSame设置为true以后，继续移动cur；当cur不等于mark时，

如果标志位isSame是true，说明前面有重复元素，即mark到cur的前一个元素，都是重复的，那么将last指向cur即可删除这些重复元素，将mark设置为cur，cur往后挪一个位置，继续移动三个指针；

如果标志位isSame是false，说明前面的元素都是不重复的，那么直接将三个指针往后挪一个位置即可。

退出循环以后，还需要单独判断isSame是不是true，如果为true，说明链表结尾的元素也是重复元素，需要单独处理。