02.01、[简单] 移除重复节点
1、题目描述
编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
2、解题思路
为了实现这一目标，我们可以使用一个哈希表（或集合）来记录已经遇到的节点值，逐步遍历链表并删除重复的节点。
具体步骤如下：
- 从链表的第一个节点开始遍历，创建一个哈希表来记录已经遇到的节点值。
- 如果遇到的节点值不在哈希表中，则将该值添加到哈希表中，并继续遍历。
- 如果遇到的节点值已经存在于哈希表中，说明该节点是重复的节点，将其从链表中删除。
- 最终返回处理后的链表。
3、代码实现与详细注释
class Solution {
public:
ListNode* removeDuplicateNodes(ListNode* head) {
// 边界条件：如果链表为空或只有一个节点，直接返回头节点
if (head == nullptr || head->next == nullptr) {
return head;
}
// 使用一个哈希表记录已经遇到的节点值
unordered_map<int, int> hash;
ListNode* cur = head; // 从链表的第一个节点开始遍历
hash[cur->val]++; // 记录第一个节点的值
// 开始遍历链表的后续节点
while (cur->next) {
ListNode* next = cur->next; // 记录当前节点的下一个节点
// 如果下一个节点的值已经在哈希表中出现过，说明是重复节点
if (hash.count(next->val)) {
// 删除重复节点：将当前节点的 next 指向下下个节点
cur->next = next->next;
} else {
// 如果下一个节点的值没有出现过，则记录该值
hash[next->val]++;
// 移动当前指针到下一个节点
cur = next;
}
}
// 返回去重后的链表头节点
return head;
}
};
4、时间与空间复杂度分析
- 时间复杂度: O(n)，其中 n 为链表的长度。我们只需要遍历链表一次，同时每个节点的值存储或查找在哈希表中的时间是常数级别。
- 空间复杂度: O(n)，因为需要使用哈希表来存储已经访问过的节点值。
这种方法效率较高，适合链表长度较大且包含重复节点的情况。
