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

首次提交成功，未优化

使用队列，元素先进，查看链表元素与队尾元素是否相同，相同时不入队，且在遇到下一个不同元素时删除队尾元素（要注意链表传入时的指向问题，要将队尾节点指向设为null）

import java.util.*;

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

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
      // 列表为空
      if (head == null) {
        return null;
      }
      // 队列
      LinkedList<ListNode> queue = new LinkedList<ListNode>();
      // 创建当前节点，后面循环判断
      ListNode curNode = head;
      int count = 1;
      while (curNode != null) {
        // 队列为空，直接加入元素
        if (queue.isEmpty()) {
          queue.add(curNode);
          curNode = curNode.next;
          continue;
        }
        ListNode node = queue.peekLast();
        // 如果当前节点值与列表最后一个值相同，则不入队，且进行记录，这里用计数方法，否则入队
        if (node.val == curNode.val) {
          count ++;
          curNode = curNode.next;
          
        } else {
          if (count > 1) {
            queue.pollLast();
            count = 1;
          }
          queue.add(curNode);
          curNode = curNode.next;
        }
      }
      // 列表结尾相同的情况
      if (count > 1) {
        queue.pollLast();
      }
      // 队列为空，说明列表中的元素都有值相同情况  
      if (queue.isEmpty()) {
        return null;
      }
      // 去除队列最后元素的指向
      queue.peekLast().next = null;
      // 队头作为返回的列表头节点
      ListNode res = queue.poll();
      if (queue.isEmpty()) {
        res.next = null;
      }
      ListNode node = res;
      // 队列中没有重复的元素构成列表
      while (!queue.isEmpty()) {
        node.next = queue.poll();
        node = node.next;
      }
      return res;
    }
}