24小时自动发货网站建设,免费申请移动手机卡,网站建设开票写什么,wordpress 黄聪02.01、[简单] 移除重复节点
1、题目描述
编写代码#xff0c;移除未排序链表中的重复节点。保留最开始出现的节点。
2、解题思路
为了实现这一目标#xff0c;我们可以使用一个哈希表#xff08;或集合#xff09;来记录已经遇到的节点值#xff0c;逐步遍历链表并删…02.01、[简单] 移除重复节点
1、题目描述
编写代码移除未排序链表中的重复节点。保留最开始出现的节点。
2、解题思路
为了实现这一目标我们可以使用一个哈希表或集合来记录已经遇到的节点值逐步遍历链表并删除重复的节点。
具体步骤如下
从链表的第一个节点开始遍历创建一个哈希表来记录已经遇到的节点值。如果遇到的节点值不在哈希表中则将该值添加到哈希表中并继续遍历。如果遇到的节点值已经存在于哈希表中说明该节点是重复的节点将其从链表中删除。最终返回处理后的链表。
3、代码实现与详细注释
class Solution {
public:ListNode* removeDuplicateNodes(ListNode* head) {// 边界条件如果链表为空或只有一个节点直接返回头节点if (head nullptr || head-next nullptr) {return head;}// 使用一个哈希表记录已经遇到的节点值unordered_mapint, 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)因为需要使用哈希表来存储已经访问过的节点值。
这种方法效率较高适合链表长度较大且包含重复节点的情况。
