删除排序链表中的重复元素（虚拟头结点技巧）

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

题目描述

Tag : 「链表」

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素只出现一次。

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

示例 1：

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

示例 2：

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

提示：

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

基本思路

还是与 82. 删除排序链表中的重复元素 II 相似的解题：

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

代码：

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;
    }   
}
复制代码

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

拓展

「重复元素全部删除」，该如何实现？

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

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 = tail.next;
            }
            // 如果 head 与下一节点相同，跳过相同节点
            while (head.next != null && head.val == head.next.val) head = head.next;
            head = head.next;
        }
        tail.next = null;
        return dummy.next;
    }
}
复制代码