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

• 相同：标记当前节点为重复节点，同时next指向下一个节点
• 不同：进一步判断当前节点之前是否为重复节点，如果是则要将其pre指向其next，如果不是则正常后移

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        //思路：分为三部分，第一部分重复，中间重复，第三部分重复
        //快慢指针法
        if(head==null||head.next==null)return head;
        boolean repeat=false;
        ListNode cur=head;
        int curval=cur.val;
        ListNode newHead=new ListNode(-9999);
        ListNode pre=newHead;
        while(cur.next!=null){
            //如果后继节点值==当前节点值
            //标记当前节点为重复节点，后继节点后移
            if(cur.val==cur.next.val){
                repeat=true;
                cur.next=cur.next.next;
            }else{
                //如果后继结点值!=当前节点值
                //但是当前节点之前发生了重复
                //那么当前节点不能保留
                if(repeat){
                    repeat=false;
                    pre.next=cur.next;
                    cur=cur.next;
                //如果当前节点之前未发生重复
                //那么当前节点是可以保留的
                }else{
                    pre.next=cur;
                    pre=cur;
                    cur=cur.next; 
                }  
            }       
        }
        //最后再判断一次最后一个节点是否也是重复节点需要删除
        if(repeat){
            repeat=false;
            pre.next=cur.next;
            cur=cur.next;
        }
        return newHead.next;
    }
}