class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def print_list(self):
        current_node = self.head
        while current_node:
            print current_node.data
            current_node = current_node.next

    def prepend(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def append(self, data):
        new_node = Node(data)

        if self.head is None:
            self.head = new_node
            return

        last_node = self.head
        while last_node.next:
            last_node = last_node.next
        last_node.next = new_node

    def insert(self, data, node):
        if not node:
            print "Node not in list"
            return

        new_node = Node(data)
        new_node.next = node.next
        node.next = new_node

    def delete_node(self, key):
        cur_node = self.head
        if cur_node and cur_node.data == key:
            self.head = cur_node.next
            cur_node = None
            return
        prev_node = None
        while cur_node and cur_node.data != key:
            prev_node = cur_node
            cur_node = cur_node.next
        if cur_node is None:
            return
        prev_node.next = cur_node.next
        cur_node = None
        return

    def delete_pos(self, pos):
        index = 0
        cur_node = self.head
        prev_node = None

        if pos == 0:
            self.head = cur_node.next
            cur_node = None
            return
        while cur_node and index < pos:
            prev_node = cur_node
            cur_node = cur_node.next
            index += 1
        if cur_node:
            prev_node.next = cur_node.next
            cur_node = None
            return
        print 'Node not in list'

    def len_iterative(self):
        cur_node = self.head
        count = 0
        while cur_node:
            count +=1
            cur_node = cur_node.next
        return count

    def len_recursive(self, node):
        if node is None:
            return 0
        return 1 + self.len_recursive(node.next)

    def swap_nodes(self, k1, k2):
        # check if keys are same
        if k1 == k2:
            return
        # start at the head
        prev_1 = None
        curr_1 = self.head
        # go through list until we hit k1
        while curr_1 and curr_1.data != k1:
            prev_1 = curr_1
            curr_1 = curr_1.next
        # go through list until we hit k2
        prev_2 = None
        curr_2 = self.head
        while curr_2 and curr_2.data != k2:
            prev_2 = curr_2
            curr_2 = curr_2.next
        # if k1 or k2 didnt exist in list
        if not curr_1 or not curr_2:
            return
        # curr_1 is our key, and prev_1 is the one before it
        if prev_1:
            prev_1.next = curr_2
        else:
            self.head = curr_2 # assume head if no previous

        # curr_2 is our key, and prev_2 is the one before it
        if prev_2:
            prev_2.next = curr_1
        else:
            self.head = curr_1 # assume head if no previous

        curr_1.next, curr_2.next = curr_2.next, curr_1.next # swap

    def print_helper(self, node, name):
        if node is None:
            print name + ": None"
        else:
            print name + ":" + node.data

    def reverse_iterative(self):
        prev = None
        curr = self.head
        while curr:
            nxt = curr.next
            curr.next = prev
            self.print_helper(prev, "PREV")
            self.print_helper(curr, "CUR")
            self.print_helper(nxt, "NEXT")
            print "\n"
            prev = curr
            curr = nxt
        self.head = prev

    def reverse_recursive(self):
        def _reverse_recursive(curr, prev):
            if curr is None:
                return prev
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
            return _reverse_recursive(curr, prev)

        self.head = _reverse_recursive(self.head, None)

    def merge_sorted(self, ll):
        p = self.head
        q = ll.head
        s = None
        if not p:
            return q
        elif not q:
            return p

        if p.data <= q.data:
            s = p
            p = s.next
        elif q.data <= p.data:
            s = q
            q = s.next

        new_head = s
        while p and q:
            if p.data <= q.data:
                s.next = p
                s = p
                p = s.next
            else:
                s.next = q
                s = q
                q = s.next

        if not p:
            s.next = q
        if not q:
            s.next = p

        return new_head

    def remove_duplicates(self):
        cur = self.head
        prev = None
        dups = dict()

        while cur:
            if cur.data in dups:
                # remove node
                prev.next = cur.next
                cur = None
            else:
                # have not encountered element before
                dups[cur.data] = 1
                prev = cur
            cur = prev.next

ll = LinkedList()

ll.append(1)
ll.append(1)
ll.append(5)
ll.append(7)
ll.append(9)
ll.append(9)
ll.append(10)

ll.remove_duplicates()
ll.print_list()
