Wednesday, December 7, 2011

Given a list and a pointer to a node delete that node.

1. Where is the trick?
Let's hope the list is double linked (seeing the kind of operation on it):

delete_node(list *l, node* n) {
if (!n or !l) return;

if (n == l) {
if (l = l->next) l->prev = 0;
} else if (n->prev->next = n->next) {
n->next->prev = n->prev;
}

delete n;
}

Enjoyed it. I have to say that I coded that completely ignoring this:

"Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live"

3. //n - node to delete
//l - pointer to first element in list
//c - current node
//p - previouse node

delete_node(list* l, node* n) {
if (!n or !l) return;
if (n !=l) { //list has at least 2 elements
for ( node* c = l->next, node* p = l;
c;
p = c, c = c->next) {
if (n == c) {
break;
}
}

assert(p and c);
p->next = c->next;
}

delete n;
}

1. So the next big question is can you extend this solution to handle cycle detection in a single linked list where you cannot use any secondary memory storage for visited nodes and you cannot manipulate the node structure itself (e.g. add a isVisited boolean)?

So basically detect this cycle and return a pointer to the beginning of the cycle (C):
A -> B -> C -> D -> E -> C -> D -> E -> C...

:)

4. The idea is to copy the contents of next node into current node, and then delete the next node. If the node to be deleted is last node, we can copy the contents of head node to last node, and delete head node. However, it will alter the list nodes.