連結リストから重複要素の削除

問題

ソートされていない連結リストから重複した要素を削除する。

考え方

一度出てきた値は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("")