In [138]:

    

#remove duplicates from unsorted linked list.
#follow up: what if no buffer is allowed.

#approch with hashtable, use extra data structure. runtime:O(n) space:O(n)
import linked_list
def RemoveDupsHash(ll):
    node = ll.head
    h = {}
    while node.next is not None:
        if h.has_key(node.next.data):
            node.next = node.next.next
        else:
            h[node.data]=1
            node = node.next
    print ll
    
#Second approach, without buffer.Runtime: O(n2) space:O(1)
def RemoveDups(ll):
    node = ll.head
    nodenext = node
    while nodenext.next is not None:
        if nodenext.next.data == node.data:
            nodenext.next = nodenext.next.next 
        else:
            nodenext = nodenext.next
    print ll


    

In [139]:

    

ll = LinkedList()
ll.insert(3)
ll.insert(2)
ll.insert(4)
ll.insert(5)
ll.insert(2)
ll.insert(4)
ll.__str__()


    

    
Out[139]:





'->4->2->5->4->2->3'

In [140]:

    

RemoveDupsHash(ll)


    

    




->4->2->5->3

In [141]:

    

ll.head.data


    

    
Out[141]:





4

In [142]:

    

RemoveDups(ll)


    

    




->4->2->5->3

In [ ]: