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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        // write code here
        //特殊值处理，如果链表为空或者链表的长度为1,此时链表没有重复元素
        if(head == null || head.next == null){
            return head;
        }
        ListNode flow = head;  //创建一个慢指针，指向链表的头节点
        ListNode fast = flow.next;  //创建一个慢指针，指向链表的第二节点
        ListNode prep = null;  //慢指针指向节点的前驱节点
        ListNode root = null;  //指向删除重复元素后的链表的头指针
        while (fast != null){  //当快指针不为空时，遍历链表
            if(flow.val == fast.val){//当快慢指针指向的节点的值相等时，往后遍历，直到找到第一个节点值不等于fast.val
                flow = fast.next;
                while (flow != null && flow.val == fast.val){//遍历链表，直到找到第一个节点值不等于fast.val或者flow为null
                    flow = flow.next;
                }
                if(flow == null){//如果flow为null
                    if(prep == null){
                        return null;
                    }else {
                        prep.next = null;
                        return root;
                    }
                }else{//找到第一个节点值不等于fast.val
                    if(prep == null){
                        prep = null;
                    }else {
                        prep.next = flow;  //更新慢指针，慢指针移动
                    }
                    fast = flow.next;   //更新快指针，快指针移动
                    if(fast == null && root == null){
                        root = flow;
                    }
                }
            }else {//当快慢指针指向的节点的值不相等时,如果此时的prep=null，则为prep赋初值
                if(prep == null){
                    root = flow;  //指向删除重复元素后的链表的头指针,最终的返回值
                }
                prep = flow;  //更新慢指针的前驱节点，慢指针的前驱节点移动
                flow = fast;  //更新慢指针，慢指针移动
                fast = fast.next;  //更新快指针，快指针移动
            }
        }
        return root;
    }
}