在单链表中存储了 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中，说明该节点为重复节点，删除该节点并更新链表结构。 - 最后得到一个不含重复绝对值节点的链表。
代码实现
数据结构定义
首先定义链表节点的数据结构：
struct Node {int value; // 节点的数值Node* next; // 指向下一个节点的指针
};
算法实现
按照上述思路，以下是完整的 C++ 代码实现：
#include "bits/stdc++.h"using namespace std;// 链表节点结构
struct Node {int value;Node* next;
}; // 去除链表中绝对值相同的节点，仅保留首次出现的节点
void search(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 函数对其进行去重操作：
int main() {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;return 0;
}
代码讲解
- 数据结构定义：定义
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) 的时间复杂度，更适合大规模链表的数据处理。
总结
本文介绍了如何在链表中去除绝对值相等的节点，仅保留首次出现的节点，并通过哈希表优化了时间复杂度。在处理去重问题时，哈希表是非常实用的数据结构，可以显著提高算法效率。
通过本题，可以进一步加深对链表操作和哈希表使用的理解，为后续更复杂的数据结构题目打下基础。
