CareerCup

Heya,
void Delete(node *p) //p is the node to be deleted
{
 if(p->next==NULL) //last node
   p->value=-1; //mark it so that when we traverse the LL, and reach this node, we do not     consider this a part of LL
 else
 {
    p->value=p->next->value;
    p->next=p->next->next;
 }
}

should the node go away (freed) or its only that the data in the node needs to go away

public bool remove(int key) //remove link with given key
{ //(assumes non-empty list)
Link pCurrent = pFirst; //search for link
Link pPrevious = pFirst;
while (pCurrent.iData != key)
{
if (pCurrent.pNext == null)
return false; //didn’t find it
else
{
pPrevious = pCurrent; //go to next link
pCurrent = pCurrent.pNext;
}
} //found it
if (pCurrent == pFirst) //if first link,
pFirst = pFirst.pNext; //change first
else //otherwise,
pPrevious.pNext = pCurrent.pNext; //bypass it
pCurrent = null; //delete link
return true; //successful removal
}

copy the content of the next node into the current node; release the memory of the next node; done

What I don't understand is how you even start to search when all you are getting is some key and no starting or any node address. He says head node is not given, then how do your even traverse the entire list.

A node in a linked list is an object. So what is meant in this question is that one is given the object depicting the node to be deleted. And the object will have the data (key) and the pointer to the next node (object) in the linked list. So the solution given by syrus is correct if the current node is not the last node.
One modification that I can think of to go around this problem is to attach a dummy node at the end of the linked list. This way the node to be deleted can never be the last node. We just make the node to be deleted (if it's second last) the dummy node.

Suppose v need to delete a node "r"
p=r->next;
r->data=p->data;
r->next=p->next;
free(p);

malloc allocates contiguous blocks of memory. so lets say our original list contains nodes: { a, b, c, d, e}. Since we dont know the head, we dont know where the list begins. now we're asked to delete node 'e' (lets say) i.e. we've been given the address of the node 'e'. now if e->next == NULL, we can be certain that 'e' is the last node to be deleted. In this case, we must fix the address pointed to by the node 'd'. But how do we reach node 'd' given node 'e'?

Since malloc allocates memory in continuous chunks, cant we reach node 'd' by doing a pointer arithmetic i.e. Address of node 'd' = Address of node 'e' - sizeof(struct node). Now we can reach node 'd' and fix its next pointer to point to NULL.

the same logic can be used for any node but the first. imagine if we have only 1 node in the list and we're asked to delete this node?

Heya,
void Delete(node *p) //p is the node to be deleted
{
 if(p->next==NULL) //last node
   p->value=-1; //mark it so that when we traverse the LL, and reach this node, we do not     consider this a part of LL
 else
 {
    p->value=p->next->value;
    p->next=p->next->next;
 }
}

Idea is very well known and It can be done in Constant time ,Having One limitation(If last node is passed)..Please have the following code snippet..

void delete(struct node *x)
{
struct node *y=NULL;

y=x->next;
x->data=y->data;
x->next=y->next;
free(y);
}
If you find any mistake then please let us know.

void Delete(struct node *ptr)
{
struct node *temp=ptr->next;
ptr->data=temp->data;
ptr->next=temp->next;
free(temp);
return ;
}

1. With a single pointer in single linked list, only middle node can be deleted, the last node cant be deleted.
All the cases can be achieved under following conditions
a. either we need two pointers in single linked list
b. or possible if it is a double linked list
c. or if malloc ensures contiguous memory allocations for the nodes
Otherwise I don't any other ways to fix the problem.
If anybody knows the solution please let me know

Well logically we can not delete the node whose address is provided as input.
so to serve the purpose the above tricks works
:)

yup, impossible!

its impossible. how can we proceed without a given head node