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

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?

• It's a single linked list Commented Jun 9, 2015 at 12:59
• Did you try Googling to see if this problem has been solved? stackoverflow.com/questions/793950/… Commented Jun 9, 2015 at 13:04
• 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. Commented Jun 9, 2015 at 13:04

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.