The best part is that with a simple refinement of what the return value means, the problem with search(B) could have been avoided. I would have done it thusly:
search(A) returns NULL
search(B) or search(C) returns the predecessor node (i.e., A or B respectively)
search(D) returns C
So my delete code could work like this:
delete (Node * node)
{
Node * nodeToDelete = head;
if (node == NULL)
head = head -> next;
else if (node -> next == NULL)
return;
else
{
nodeToDelete = node -> next;
node -> next = nodeToDelete -> next;
}
delete nodeToDelete;
return;
}
Pardon the crappy formatting. I'm sick of fighting with the editor. But you get the idea.