Thursday, December 16, 2010

Linked List : Given a pointer to any node, delete the node pointed by the pointer

Given a linked list like this,


Given a pointer to any node, delete the node pointed by the pointer. Note: no head pointer is given.

Solution:

Assume a pointer to p3, lets call it to 'p'. Since only pointer to current node is provided, there is no way to delete the current node from the list. But instead of deleting the current node, we can just move the next node data to current node and delete the next node. The algorithm can be explained simply as,
p->data = p->next->data;
t = p->next;
p->next = p->next->next;
delete t;

Cheers!!
Jack

2 comments:

Mani said...

This works as long as the given node is not the tail of the linked list. It might not work if the node given is the tail...

bragadeesh said...

@mani: thanks for the insight. if the given node is the tail, we can as well add a condition to check whether its the last node and simply destroy it.

code;
if(p->next == null){
delete p;
return;
}