Θ(1) algorithm that removes one element from a linkedlist

Question

I have to find a Θ(1) solution to the following problem:

You're given a singly linked list and a reference to one of the elements in the list. You can be certain that this is not the last element in the list. Find an Θ(1) algorithm that removes this element from the linkedlist.

Image that I have to remove 99 from the next list. I was thinking of replacing the value 99 with a pointer to the next element and thus just skipping this element whenever you loop over it, but I don't think that's a very neat way to do this.

Any ideas on how to solve this problem?

Answer 1

Simple:

• Set the value of that node to the value of the next node.

• Remove the next node from the linked list.

In Python code (as it is closest to executable pseudocode easily translated to your poison of choice):

def remove_node(node):
    node.value = node.next.value
    node.next = node.next.next

It's a common coding puzzle. Note that the description clearly states that [y]ou can be certain that this is not the last element in the list, thus guaranteeing that there is a next node to nick the value from.