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 way over my head! by drew)

I've got two questions:

1. Can you not overload the -> operator and get it to point at the next element instead? I suppose you would have issues with the next pointer of the previous node getting pointed to a null pointer in the case of the last element

2. Can you do the following (if the nodes are the same size):

//Say you have the address to node N
//Get the pointer to the next node
Node * next = N->getNext() ;
//overwrite the current node with the next node
memcpy(N, next, sizeof(N)) ;
//remove the next pointer from the next node
next->setNext(0) ;
//delete the next node (which has now been copied to the original address)
delete next ;

Posted by Rushi on 2003-11-25 12:18:42