经典题再升级：删除排序链表中的重复元素

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

这是 LeetCode 上的 82. 删除排序链表中的重复元素 II ，难度为中等。

Tag : 「链表」

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中没有重复出现的数字。

返回同样按升序排列的结果链表。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
复制代码

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]
复制代码

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

基本思路

几乎所有的链表题目，都具有相似的解题思路。

建一个「虚拟头节点」dummy 以减少边界判断，往后的答案链表会接在 dummy 后面
使用 tail 代表当前有效链表的结尾
通过原输入的 head 指针进行链表扫描

我们会确保「进入外层循环时 head 不会与上一节点相同」，因此插入时机：

head 已经没有下一个节点，head 可以被插入
head 有一下个节点，但是值与 head 不相同，head 可以被插入

代码：

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (head != null) {
            // 进入循环时，确保了 head 不会与上一节点相同
            if (head.next == null || head.val != head.next.val) {
                tail.next = head;
                tail = head;
            }
            // 如果 head 与下一节点相同，跳过相同节点
            while (head.next != null && head.val == head.next.val) head = head.next;
            head = head.next;
        }
        tail.next = null;
        return dummy.next;
    }
}
复制代码

时间复杂度： $O(n)$
空间复杂度： $O(1)$

拓展

如果问题变为「相同节点保留一个」，该如何实现？

83. 删除排序链表中的重复元素

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return head;
        ListNode dummy = new ListNode(-109);
        ListNode tail = dummy;
        while (head != null) {
            // 值不相等才追加，确保了相同的节点只有第一个会被添加到答案
            if (tail.val != head.val) {
                tail.next = head;
                tail = tail.next;
            }
            head = head.next;
        }
        tail.next = null;
        return dummy.next;
    }   
}
复制代码