連結リストから重複要素の削除
問題
ソートされていない連結リストから重複した要素を削除する。
考え方
一度出てきた値はhash tableに保存しておいて、もう一度出たら削除する。 一度リスト全体を見ればいいので、時間計算量はO(N)
コード例
# 双方向連結リスト class LinkedList(): def __init__(self, d, n=None, p=None): self.data = d self.prev = None self.next = None self.setNext(n) self.setPrevious(p) def setNext(self, n): self.next = n if(n != None) and (n.prev != self): n.setPrevious(self) def setPrevious(self, p): self.prev = p if(p != None) and (p.next != self): p.setNext(self) def deleteNode(n): """ node nを削除する、前後のnodeの変数も書き換える """ prev = n.prev next = n.next if(prev != None): prev.setNext(next) if(next != None): next.setPrevious(prev) def deleteDuplicate(head): """ listの先頭を与える """ if head.prev : print("error! this node is not head") return -1 hash = {} node = head while node: next = node.next if node.data in hash.keys(): # type of keys is set deleteNode(node) else: hash[node.data] = 1 node = next return hash.keys() if __name__ == "__main__": link=None for i in range(10): link = LinkedList(i%3, n=link, p=None) print("元のデータ") _ = link print("%d" % _.data, end="") while(_.next): # nodeがNoneでない間回る。 _ = _.next print(" -> %d"%_.data, end="") temp = deleteDuplicate(link) print("\n変更後") _ = link print("%d" % _.data, end="") while(_.next): # nodeがNoneでない間回る。 _ = _.next print(" -> %d"%_.data, end="") print("")