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)?

(In reply to re: Seems simple enough by SilverKnight)

Hum...tricky....I suspect there is something you are not telling me, or are asuming that I am not, or vice versa.

Is the list contiguous in memory (ie, consists of constant sized elements taken from a single array, but linked in some different order)?

I'm assuming the elements are separately allocated, and so have no particular ordering/location in memory.

Assuming you don't intend to search all of allocated memory, I don't see how you can possibly resurrect the parent of the current element without a pointer to somthing above it. I will think on this, and look forward to the solution....

Posted by Brian Wainscott on 2003-11-24 18:13:58