Amazon Interview Question Software Engineer / Developers
Teja is right.
If we do that, it takes only O(1) in almost all the case except when deleting last node.
void deleteNode(link* root, link* node){
if (node -> next == NULL){
//find the previous node - O(n)
link *temp = root;
while (temp != NULL && temp -> next != node){
temp = temp -> next;
}
if (temp == NULL) return;//not found
temp-> next = NULL;
delete node;
}
else {
//copy content - //O(1)
link *temp;
temp = node -> next;
node->data = temp -> data;
node->next = temp -> next;
delete temp;
}
}
your else statement is right but how did u get the root, the question says you are ONLY given the node to delete. One cannot cannot delete the last node with this approach. So your solution is partially correct.
Given a pointer to a node, it is not possible to go back from that node using this pointer. So it can be assumed that either the current node or one of the following node has to be deleted.
struct list *temp = *node;
*node = temp->next;
free(temp); // this will free the location occupied by the node to the deleted.
Comments ?
Given a pointer to a node, it is not possible to go back from that node using this pointer. So it can be assumed that either the current node or one of the following node has to be deleted.
struct list *temp = *node;
*node = temp->next;
free(temp); // this will free the location occupied by the node to the deleted.
Comments ?
temp is the given node then
temp->data = temp->next->data;
temp->next = temp->next->next;
free(temp->next);
does this sound right???
ptr - the pointer to the node to be deleted.
head - the pointer to the header of the list.
if (head == null) return ; // list is empty
if (ptr == head) //ptr points to the first node-delete first node.
{
head=head->next;
}
else // if the node to be deleted is not the first node
{
while(head->next != ptr && head->next != null)
head = head->next; // Traverse to the previous node of ptr.
if (head->next == null) return ;//reached the end of the list, didn't find ptr.
head->next = ptr->next; // actual delete statement.
}
free(ptr); //release ptr's memory.
}
Guys, if you are given a pointer to the last node and nothing else then you can't delete it. Don't try so hard. But that is a special case and I believe you must have the root node available.
Whats wrong about just deleting that node? The previous node shall just point to null and shall be the new tail.
Whats so hard about it?
@ERN PFB defination of pointer for ur reference.
Q:what is a pointer?
A:A pointer references a location in memory, and obtaining the value at the location a pointer refers to is known as dereferencing
so if head is not given and u r deleting last node... its ok u free the memory of last node BUT second last node->link still hav some address (address not value).now free memory do not necessary to hold NULL.It can be any thing "Garbage Value" .
Copy the contents of next node to current node.. and delete next node..
- Teja February 02, 2010