Θ(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.

enter image description here

Any ideas on how to solve this problem?

• Pieter Verschaffelt: It's a single linked list
• mclark1129: Did you try Googling to see if this problem has been solved? stackoverflow.com/questions/793950/…
• Kilian Foth: This is a very well-known think-outside-the-box interview question. The solution is to not delete the node you're given, but to copy the next value into it and then delete the next node.

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.