Algorithm for deleting one element in an single linked list with O(1) complexity

Question

I'm a student of computer science in Germany. My professor gave use the following question to think about:

'Given a reference to a node in a single linked list (which is not the last node). Give an algorithm to delete this element from the list which has O(1) complexity while maintaining the integrity'.

I thought about this, but I'm pretty sure, that there is no such algorithm. since it is a single linked list, you must loop through every node in the list until you reach the node which should be delete, because you have to modify the next-Pointer in the node before the deleted. Which would lead to O(n) complexity.

Am I missing anything?

Answer 1

It depends on whether or not the nodes are mutable (in value).

There is a way of doing it, if you can do what you like with the nodes:

toDelete.value = toDelete.next.value
toDelete.next = toDelete.next.next

All the information from toDelete has now been overwritten, by the information in the old toDelete.next. (Depending on the platform, you may then need to free the old toDelete.next - which means keeping a temporary reference to it. Not good if anyone else still has a reference to it, of course. In Java/C# you'd just ignore it.)

I tried to work out a way of hinting at it without giving it away, but it's kinda tricky...

It does rely on this not being the last node in the list though.