首页 > 代码库 > 13.删除单链表中重复的元素
13.删除单链表中重复的元素
13.删除单链表中重复的元素
思路：
用Hashtable辅助，遍历一遍单链表就能搞定。同高级函数9的原因，我不太会使用C++STL中的hash。而如果使用set集合来存储链表中的所有的值，实际上效率和每次重新遍历单链表是一样的。“用了c++标准库中的set来保存访问过的元素，所以很方便的就可以判断当前节点是否在set集合中，直接使用set提供的find函数就可以了。而且使用set的查找在时间复杂度上比较低。”我不太清楚STL中set集合的实现方式，如果是基于类似hash结构的话，那自然效率O(1),而如果是数组的话，实际在遍历一遍，所以效率O(n)。不过貌似后者的可能性大一些。
void DeleteDuplexElements(Node*Head);
//删除单链表中的重复元素（使用set集合来实现）void DeleteDuplexElements(Node*Head){ if(Head==NULL||Head->next==NULL) //链表为空或者只有一个元素 { return ; } //以下至少有两个元素 set<int>s; Node* p1=Head; Node* p2=Head->next; s.clear(); s.insert(p1->value); while(p2!=NULL) //要删除的不可能是链表头，因为如果是链表头，则集合还为空 { if(s.find(p2->value)==s.end()) //没有 { s.insert(p2->value); p2=p2->next; p1=p1->next; } else //已经有，则要删除该节点 { if(p2->next==NULL) //如果是链表尾 { p1->next=NULL; free(p2); p2=NULL; } else { p1->next=p2->next; free(p2); p2=p1->next; } } }}
13.删除单链表中重复的元素
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。