题解 | #删除有序链表中重复的元素-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 node) {
        if(node==null){
            return null;
        }
        ListNode vnode = new ListNode(0); // 虚拟节点, 解决边界问题
        vnode.next = node;
        ListNode pre = vnode; // 标记最近一个可选元素
        ListNode left = node; 
        ListNode right = node.next;
        boolean flag = false;
        while (right != null) { 
            if (left.val == right.val) { // 如果相邻元素相等, 则标记需要删除一次, 左不动, 右挪一步
                right = right.next;
                flag = true;
            } else { // 如果相邻元素不等, 需要分情况
                if (flag) { // 如果需要删除一次, 说明是当前重复元素走完了, 要换元素了
                    pre.next = right; // 此时直接跳过重复元素, 等同删除
                    left = right; // 左右都挪一步
                    right = right.next;
                    flag=false; // 删除重复元素后, 标记清空
                } else { // 如果不需要删除一次, 说明没有重复元素, 只需要3个指针都挪一步就行了
                    pre = pre.next;
                    left = left.next;
                    right = right.next;
                }
            }
        }
        if (flag) {// 如果元素走完了, 还有个删除标识, 说明最后几个都是重复元素, 此时抛弃pre后面的所有重复元素即可
            pre.next = null;
        }

        return vnode.next;
    }
}