You have a SINGLY linked list in memory of at least 1000 nodes (perhaps many more). I give you a pointer to ONE of the elements. (You don't know to which one.)

Upon examination, you discover that the pointer to the next node is not NULL (indicating that we're not at the last node in the list).

Your mission, should you decide to accept it, is to delete the current node, and maintain the valid linked list.

First, how do you go about doing that?

Second, how do you go about doing that in fixed space (i.e., you have only 64 bytes of memory as scratch space, so you can't replicate the rest of the linked list in memory, nor store more than 16 4-byte pointers)?

I was gone for a week and a half, and it's sad that I missed this problem being posted; I was looking forward to it when I saw it in the queue.

My first thoughts were the same as Brian's; you need a pointer to the head of the list, and would need to traverse the list until you the node after the current node is the one you want to delete. Then, you change the next-node pointer to the one after, and delete the one you want to. That can be done is fixed space, but not in constant time (it will be O(n)). That's the normally cited approach to deleting a node in a singly-linked list.

After SK's comments suggested that you don't have a pointer to the head of the list, the problem changes. Because it is singly linked, you access the previous node, but you need to change the pointer of that node to the one after it. That got me thinking, and actually the process is more efficient if you don't use the head of the list anyway.

You will not actually have to delete the node you are pointing to, but you will delete the value of the node you are pointing to. I'm assuming that's what SK was intending here; because otherwise the problem is indeed impossible. You just assign the current node the value and the next-node pointer from the one following it, and the delete that node from memory.

Here's a short function that takes a pointer (iterator) to an element of a singly-linked list and effectively deletes it (although that actual node is not deleted):

template <ptr>


eraseElement(ptr p) {


  **p = *((*p).next);


  (*p).next = ((*p).next).next;


  delete p.next;


}

That should work, I think.
I didn't actually implement a singly-linked list and test it, but if you have a pointer to a node, and next is a member variable of a node that is a pointer to the next node, that should work, conceptually.

Problems arise here if, say, you have a pointer elsewhere in your program to the node after the one you want to delete, and then you try to use that pointer; so while this is more efficient, it's preferable to traverse the list from the head (in O(n) time) and delete the physical node in question. Given the problem, though, I'm assuming that's what he had in mind.

Posted by DJ on 2003-12-01 13:21:46