Deleting any node from a single linked list when only pointer to that node is given

Question

This is a question posed to me in an interview.

"A single linked list is there in the memory. You have to delete a node. You need to write a function to delete that node, which takes only the address of the node to be deleted as input and nothing else(including head)"

I gave the answer similar to the one answered in the below post -- Copying the contents of the next node into the node to be deleted and deleting the next one.

Deleting a middle node from a single linked list when pointer to the previous node is not available

But the interviewer asked me again, what if I pass the address of the last node. I told him, since the next will be a NULL, copy that NULL into the data field along with the address to the next node which is also NULL. Then he told me there will be a problem of dangling pointers... which I didn't understand a bit. Can some one please throw light into this problem ? Is there a generic solution to this ?

Update (Two days later) : A little bit additional. Considering there is no special node at the end of the list. And the last node points to NULL and if that node is given as input, how to make the before last node point to NULL. Or is it impossible ?

Simply put : If a node is given as input to a function, how to make the pointer that references it, point to NULL

Answer 1

Steps:

1. Copy data from Node(i+1) to Node(i)
2. Copy the NEXT of second Node(i+1) into a temporary variable.
3. Now Delete the second Node(i+1) // it doesn't require pointer to the previous node.

Function:

void delete_node(node* node)
{
    node->Data = node->Next->Data;
    node* temp = node->Next->Next;
    delete(node->Next);
    node->Next = temp;
}

Answer 2

Dangling Pointer:

(http://en.wikipedia.org/wiki/Dangling_reference)

Dangling pointers and wild pointers in computer programming are pointers that do not point to a valid object of the appropriate type. These are special cases of memory safety violations.

Dangling pointers arise when an object is deleted or deallocated, without modifying the value of the pointer, so that the pointer still points to the memory location of the deallocated memory. As the system may reallocate the previously freed memory to another process, if the original program then dereferences the (now) dangling pointer, unpredictable behavior may result, as the memory may now contain completely different data.

In your answer, to delete the given node you actually delete the next node, which might be being referenced by a pointer. That's how dangling pointer problem arise.

(1) There are no outside references to the list, as you clarify in a note. (2) Dangling pointer problem can arise, as the interviewer said.

Both (1) and (2) cannot be correct at the same time. Which means there is a misunderstanding somewhere.

About Deleting the Last Node:

But the interviewer asked me again, what if I pass the address of the last node. I told him, since the next will be a NULL, copy that NULL into the data field along with the address to the next node which is also NULL.

I think you are confusing these two things: (1) A pointer p that points to NULL, (2) A linked list node that has NULL in its data field.

Suppose the data structure is a -> b -> c -> d. Writing NULL to d's data field will not magicly make c to have a NULL pointer in its next field.

You can delete the last node if the linked list always has a special last node that will never be deleted. For example, a -> b -> c -> d -> LAST where LAST has a special value in its data field that denotes it is really the last element. Now to delete d, you could delete LAST and write the special value in d's data field.

Maybe these are exactly what you tried to tell during the interview, in which case there must have been some miscommunication between you and the interviewer.