问答题 14 /23

一个没有排序的链表，比如list={a,l,x,b,e,f,f,e,a,g,h,b,m}，请去掉重复项，并保留原顺序，以上链表去掉重复项后为newlist={a,l,x,b,e,f,g,h,m}，请写出一个高效算法(时间比空间更重要)。

参考答案

建立一个hash_map，key为链表中已经遍历的节点内容，开始时为空。
从头开始遍历链表中的节点：
- 如果节点内容已经在hash_map中存在，则删除此节点，继续向后遍历；
- 如果节点内容不在hash_map中，则保留此节点，将节点内容添加到hash_map中，继续向后遍历。

查看讨论

上一题下一题

扫一扫，把题目装进口袋