2

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?

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

1 Answer 1

9

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.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.