一个没有排序的链表，比如list={a,l,x,b,e,f,

[问答题]

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

查看答案及解析

推荐

manlan

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

编辑于 2015-02-09 11:40:13 回复(0)

davvy

思想是用哈希实现，用空间换取时间，把相同的元素散列到同一个槽位，起到去重的效果。

用python实现，即采用dict结构，且可以保持顺序不变：

class Solution:
    def __init__(self, L):
        self.L = L

    def unique(self):
        D = {}
        K = []
        for c in self.L:
            if c not in D.keys():
                K.append(c)
                self.D[c] = 1
        return K

编辑于 2019-03-04 11:27:00 回复(0)