一、知识点:
HashSet、链表
二、文字分析:
算法的实现思路如下:
- 如果链表为空或只有一个节点,直接返回原链表。
- 创建一个HashSet集合
seen
,用于存储已经出现过的元素值。 - 将链表头结点的值添加到
seen
中。 - 初始化两个指针
prev
和curr
,分别指向当前节点和下一个节点。 - 使用循环遍历链表,直到当前节点
curr
为null。 - 在每一次循环中,先判断
curr
节点的值是否已经出现过,如果是,则说明是重复节点,删除它。将prev
节点的next
指针指向curr
节点的下一个节点。 - 如果
curr
节点的值没有出现过,将其添加到seen
集合中,并更新prev
节点为curr
节点。 - 将
curr
指针移动到下一个节点。 - 返回更新后的链表头结点
head
。
该算法使用了HashSet集合来判断链表中的元素是否重复,从而删除重复节点。时间复杂度为O(n),其中n是链表的长度,需要遍历整个链表。空间复杂度为O(n),因为需要使用HashSet集合存储已经出现过的元素值,最坏情况下需要存储所有节点的值。
三、编程语言:
java
四、正确代码:
import java.util.HashSet; public class Solution { public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) { return head; } // 创建一个集合用于存储已经出现过的编号 HashSet<Integer> seen = new HashSet<>(); seen.add(head.val); ListNode prev = head; ListNode curr = head.next; while (curr != null) { if (seen.contains(curr.val)) { // 删除重复节点 prev.next = curr.next; } else { // 将新的编号添加到集合中 seen.add(curr.val); prev = curr; } curr = curr.next; } return head; } }