推荐 网页游戏_学服装设计的基础_济南今日头条新闻_网络广告的类型有哪些

原题地址：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);  // 将当前值加入 maptemp = temp.next;  // 移动指针} else {// 如果已存在该值，则跳过该节点temp.next = next.next;  // 删除重复节点}}// 返回去掉虚拟头节点后的链表return dummy.next;}
}

复杂度分析

1. 时间复杂度：

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

2. 空间复杂度：

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