问题描述

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Return the linked list sorted as well.

删除有序列表中所有重复的数字。

举个例子：

Example 1:
Input: 1->2->3->3->4->4->5
Output: 1->2->5

Example 2:
Input: 1->1->1->2->3
Output: 2->3

类似题目：

[83] Remove Duplicates from Sorted List{:target=”_blank”}

解法1

Thanks @jinwu{:target=”_blank”}

这道题有两个需要特别注意的地方：

第一，比较前一个结点pre的下一个结点与当前结点cur是否相等，而不是比较各自的值。

第二，为了避免连续出现不同重复数字的场景，先"虚连接"： pre.next = xxx

来看下示意图：

来看下实现：

class Solution {
    public ListNode deleteDuplicates(ListNode head) {

        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;

        while (cur != null){
            // 1. Navigate to the last dup node.
            while (cur.next != null && cur.val == cur.next.val){
                cur = cur.next;
            }

            // 2. Non duplication.
            if (pre.next == cur){
                pre = pre.next;
                cur = cur.next;
            } else {
                // key
                pre.next = cur.next;
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

Enjoy it !