2.1 Write code to remove duplicates from an unsorted linked list.
How would you solve this problem if a temporary buffer is not allowed?

I will use single linked list here. The definition of a node is given below:
``````class node:
def __init__(self, data = None):
self.data = data
self.next = None``````
Brute force solution takes O(n^2):
``````def delete_duplicates(head):
# For each node in the linked list
# Iterate all nodes after it and
# delete the duplicates
while p != None:
next = p.next
# Delete p from linked list
pre.next = p.next
else:
pre = p
p = next

if __name__ == "__main__":
n1 = node(4)
n2 = node(1)
n3 = node(1)
n4 = node(1)
n5 = node(2)
n1.next = n2
n2.next = n3
n3.next = n4
n4.next = n5

n = n1
print "Before deleting duplicates"
while n != None:
print n.data
n = n.next
delete_duplicates(n1)
n = n1
print "After deleting duplicates"
while n != None:
print n.data
n = n.next``````
Inspired by the word "unsorted" in the problem, I tried to sort a linked list with quicksort, which is the key part of a solution that costs O(nlgn). However, the quicksort for linked list is very difficult to implement (I am still trying). Furthermore, Wikipedia says that quicksort for linked list suffers from poor pivot choices without random access.

Then I turned to the answer page and found that hashtable showed its magic again:
``````def delete_duplicates(head):
# Hashtable for marking the ocurrence of data
dic = {}

# The node right before the one under processing