BM16 删除有序链表中重复的元素-II

（java实现）

题目描述：

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为1→2→3→3→4→4→5, 返回1→2→5.
给出的链表为1→1→1→2→3, 返回2→3.
数据范围：链表长度0≤n≤10000，链表中的值满足 ∣val∣≤1000
要求：空间复杂度 O(n)，时间复杂度 O(n)
进阶：空间复杂度 O(1)，时间复杂度 O(n)

输入描述：

输出描述：

示例1：

输入

{1,2,2}

输出

{1}

示例2：

输入

{}

输出

{}

问题分析：

开始的头结点可能会重复，最后结果可能为空，需要建立一个头结点。

相关知识：

链表的操作

参考代码：

思路一实现：

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
        if (head == null) {
            return null;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode cur = dummy;
        ListNode pre = dummy.next;
        while (pre!=null && pre.next!=null) {
            if (pre.val == pre.next.val) {
                int x = pre.val;
                while (pre!=null && pre.val == x) {
                    cur.next = pre.next;
                    pre = pre.next;
                }
            } else {
                cur = cur.next;
                pre = pre.next;
            }
        }
        return dummy.next;
    }
}