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

Call the given element N.

We are going to have to reset the "next" pointer of the element that points to N, and the only way to find it is to start at the top. So I don't see that we have any choice.....

Presuming H is a pointer to the head of the list (SK has to have given us at least this much, since he indicates the list is not circular), I'd do two things:

one (with beautiful indenting removed because I don't know how this system works):

if(H==N)
H=N->next;
else {
K=H;
while(K->next != N)
K=K->next;
K->next = N->next;
}

two:
question who would singly link such a long list

Posted by Brian Wainscott on 2003-11-24 16:39:58