一、知识点:
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;
}
}

京公网安备 11010502036488号