Chapter 2 Linked Lists

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?

First of all, we should ask the interviewer which kind of linked list is used, single linked list or doubly linked list? 

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

if __name__ == "__main__":
    n1 = node(4)
    n2 = node(1)
    n3 = node(1)
    n4 = node(1)
    n5 = node(2) = n2 = n3 = n4 = n5
    n = n1
    print "Before deleting duplicates"
    while n != None:
        n =
    n = n1
    print "After deleting duplicates"
    while n != None:
        n =
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 = {}
    dic[] = True
    # The node right before the one under processing
    node_pre = head
    while != None:
        node_current =
        if dic.has_key(
            # Delete the node
            del node_current
            dic[] = True
            node_pre = node_current
If the hash function is good enough, the solution above only takes O(n).;