leetcode83:删除链表中的重复元素

原题地址：83. 删除排序链表中的重复元素 - 力扣（LeetCode）

题目描述

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

解题思路

1. 问题概述：

   • 给定一个排序链表，删除所有的重复元素，使得每个元素只出现一次。

2. 问题分析：

   • 本题与 Leetcode 82 中的题目非常相似，但区别在于此题只需要删除重复的元素，而不需要处理节点的连续重复值（即删除所有重复节点，而不是仅删除包含重复的节点）。

3. 解题思路：

   • 由于链表是排序的，重复的元素一定是相邻的，因此可以使用一个遍历指针逐个检查节点值是否重复。
   • 使用一个 map 存储已经出现过的节点值，检查当前节点值是否已经存在：
     • 如果不存在，保留该节点，将其值加入 map。
     • 如果存在，则跳过当前节点，即 temp.next = temp.next.next。

4. 具体步骤：

   • 通过一个 dummy 节点指向链表头，避免处理头节点的特殊情况。
   • 遍历链表的过程中，将每个节点的值添加到 map 中，若该值已存在则跳过该节点。
   • 最终返回去掉虚拟头节点后的链表

源码实现

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        // 如果链表为空，直接返回空链表
        if (head == null) {
            return head;
        }

        // 设置虚拟头节点，避免处理头节点的特殊情况
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        // cur 指针初始化为虚拟头节点
        ListNode temp = dummy;

        // 使用 HashMap 存储已出现的节点值
        Map<Integer, Integer> map = new HashMap<>();

        // 遍历链表
        while (temp != null) {
            ListNode next = temp.next;

            // 如果下一个节点为空，则终止遍历
            if (next == null) {
                break;
            }

            // 如果 HashMap 中不存在该值，则保留该节点
            if (!map.containsKey(next.val)) {
                map.put(next.val, next.val);  // 将当前值加入 map
                temp = temp.next;  // 移动指针
            } else {
                // 如果已存在该值，则跳过该节点
                temp.next = next.next;  // 删除重复节点
            }
        }

        // 返回去掉虚拟头节点后的链表
        return dummy.next;
    }
}

复杂度分析

1. 时间复杂度：

   • 遍历链表一次，对于每个节点，查找 map 中是否存在该值，以及对 map 进行插入操作的时间复杂度为 O(1)。
   • 因此，时间复杂度为 O(n)，其中 n 是链表的长度。

2. 空间复杂度：

   • 使用了一个 HashMap 来存储已出现的节点值，在最坏情况下，所有节点的值都是不同的，因此 map 中的元素个数最大为 n。
   • 因此，空间复杂度为 O(n)。