【每日一题】2015考研数据结构 - 求不重复的链表元素
在单链表中存储了 m 个整数，每个节点由两部分组成：[data][link]，其中 data 是整数，且满足 |data| < n（n 为正整数）。
现要求设计一个高效的算法来处理链表中 data 绝对值相等的节点，只保留首次出现的节点，删除其余绝对值相等的节点。
例如，对于以下链表：
1 -> 2 -> -2 -> 3 -> null 经过处理后，得到的链表为：
1 -> 2 -> 3 -> null 解题思路
本题的关键在于高效去重，即在链表中保留首次出现的数值对应的节点，而删除其他绝对值相等的节点。可以借助 哈希表（unordered_set） 来记录已经出现过的节点绝对值。这样，我们可以在遍历链表的同时，实时判断是否存在绝对值重复的节点。
如果你不知道什么是set与实践复杂度的话可参考以下文章C++ 新手指南：如何使用 set 和 unordered_set【数据结构】时间复杂度和空间复杂度是什么？
具体思路如下：
- 从链表头开始遍历，使用一个哈希表
sets来记录出现过的节点绝对值。 - 如果当前节点的绝对值没有出现在
sets中，则将该节点的绝对值插入sets，并继续遍历。 - 如果当前节点的绝对值已经出现在
sets中，说明该节点为重复节点，删除该节点并更新链表结构。 - 最后得到一个不含重复绝对值节点的链表。
代码实现
数据结构定义
首先定义链表节点的数据结构：
structNode{int value;// 节点的数值 Node* next;// 指向下一个节点的指针};算法实现
按照上述思路，以下是完整的 C++ 代码实现：
#include"bits/stdc++.h"usingnamespace std;// 链表节点结构structNode{int value; Node* next;};// 去除链表中绝对值相同的节点，仅保留首次出现的节点voidsearch(Node* node){ unordered_set<int> sets;// 用于存储出现过的节点绝对值 Node* prev = node;// 记录上一个节点while(node !=nullptr){// 判断当前节点的绝对值是否在哈希集合中if(sets.find(abs(node->value))== sets.end()){ sets.insert(abs(node->value));// 插入当前节点的绝对值 prev = node;// 更新前驱节点 node = node->next;// 移动到下一个节点}else{// 如果绝对值已存在，删除当前节点 prev->next = node->next; Node* n = node; node = node->next;free(n);// 释放删除的节点}}}测试代码
测试代码如下，构建了一个示例链表并调用 search 函数对其进行去重操作：
intmain(){ Node* head =new Node{1,new Node{2,new Node{-2,new Node{3,nullptr}}}}; Node* cur = head; cout <<"原链表: ";while(cur !=nullptr){ cout << cur->value <<" "; cur = cur->next;} cout << endl;search(head); cur = head; cout <<"去重后的链表: ";while(cur !=nullptr){ cout << cur->value <<" "; cur = cur->next;} cout << endl;return0;}代码讲解
- 数据结构定义：定义
Node结构体，包含一个value和一个next指针，分别表示节点的数值和下一个节点的地址。 - 去重逻辑：
- 利用哈希集合
sets来存储已访问的绝对值。在遍历过程中，检查sets中是否存在当前节点的绝对值。 - 如果不存在，则将绝对值加入集合并继续遍历。
- 如果存在，则说明当前节点重复，通过调整前驱节点
prev的指针，跳过该节点并释放其内存。
- 利用哈希集合
- 时间复杂度：由于哈希表的插入、查找操作平均复杂度为
O(1)，因此整体算法的时间复杂度为O(m)，其中m是链表的节点个数。 - 空间复杂度：由于使用了一个哈希集合来记录绝对值，最坏情况下需要
O(m)的空间。
复杂度分析
- 时间复杂度：遍历链表的复杂度为
O(m)，每次检查和插入哈希表的时间复杂度为O(1)，因此总的时间复杂度为O(m)。 - 空间复杂度：使用了一个
unordered_set记录已访问的绝对值，因此空间复杂度为O(m)。
与其他方法的比较
另一种可能的思路是，使用两重循环遍历链表并删除重复节点。但这种方法的时间复杂度为 O(m^2)，效率较低。而本算法通过哈希表实现了 O(m) 的时间复杂度，更适合大规模链表的数据处理。
总结
本文介绍了如何在链表中去除绝对值相等的节点，仅保留首次出现的节点，并通过哈希表优化了时间复杂度。在处理去重问题时，哈希表是非常实用的数据结构，可以显著提高算法效率。
通过本题，可以进一步加深对链表操作和哈希表使用的理解，为后续更复杂的数据结构题目打下基础。
