Problem 2.3: Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node.
EXAMPLE
Input: the node 'c' from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e
At first sight, it is impossible to solve it without information of the left segment of the linked list. However, I quickly found that we can not only reorganize relations among nodes, but also change the data of nodes. The solution is given below:
class node:
def __init__(self, data = None):
self.data = data
self.next = None
def delete_middle(node):
# Shift the values of nodes
# and the value of given node will
# be overwritten (deleted)
node_pre = None
while node.next != None:
node_pre = node
node.data = node.next.data
node = node.next
# Delete the last node
node_pre.next = None
del node
However, my solution is not better than the one answer page. Actually, we can just shift once and delete the next node.
def delete_middle(node):
node.data = node.next.data
node_next = node.next
node.next = node.next.next
del node_next
Next time when I come up with a idea that seems "smart", I should try to verify it and improve it, rather than implement it.