# Delete Middle Node: Implement an algorithm to delete a node in the middle of
# singly linked list, given only access to that node

from LinkedList import Node, LinkedList

def delete_middle_node(node_to_delete):
    if node_to_delete.next is None:
        raise Exception("Invalid node to delete")
    node_to_delete.data = node_to_delete.next.data
    node_to_delete.next = node_to_delete.next.next


if __name__ == '__main__':
    ll = LinkedList()
    continue_ans = raw_input("Do you want to add new node? (y/n): ")
    to_delete = "n"
    while continue_ans == 'y':
        data = raw_input("Enter data for the new node: ")
        data_node = Node(data)
        ll.append_node(data_node)
        if to_delete == 'n':
            to_delete = raw_input("Is this the one you want to remove? (y/n): ")
            if to_delete == 'y':
                node_to_delete = data_node
        continue_ans = raw_input("Do you want to add new node? (y/n)?")

    print "Initial linked list: {}".format(ll)
    print "Middle node to delete: {}".format(node_to_delete)
    delete_middle_node(node_to_delete)
    print "Linked list after deletion: {}".format(ll)
