题解 | #删除有序链表中重复的元素-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
        if (head == null) {
            return head;
        }
        ListNode p = head;
        ListNode q = head.next;
        ListNode ans = new ListNode(0);
        ans.next = head;
        ListNode pp = ans;
        while (q != null) {
            if (q.val != p.val) {
                pp = p;
                q = q.next;
                p = p.next;
            } else {
                while (q != null&&q.val == p.val) {
                    q = q.next;
                }
                if (q == null) {
                    pp.next = q;
                } else {
                    pp.next = q;
                    p = q;
                    q = q.next;
                }
            
            }
        }
        
        return ans.next;
    }
}

采用双指针的解法p指向前一个元素，q指向后一个元素，当p和q指向的元素不同时，p、q向后面移动一个单位。当p、q指向的元素相同时，q往后移动直到寻找到一个不同的元素，然后将p前一个的元素的next指向q，完成重复数据的剔除；

技巧：在head之前插入一个虚拟的头指针，用来记录初始状态的p的前一个元素。