Facebook Interview Question
Software Engineer / Developersint delete (node** head,int k)
{
if(*head->val == k)
{
node* temp=*head;
*head=*head->next;
free(temp);
return 0;
}
node **n=head;
while(*n->next->val!=k && *n->next)
{
*n=*n->next;
}
if(*n->next)
{
node* temp=*n->next;
*n->next=*n->next->next;
free(temp);
return 0;
}
return -1;
}
This will miss the special case where the entire list is made up of nodes of value k. Instead of an if(), your first case should be while(*head->val == k) :)
in C#:
Node Delete(Node head, int k) // return node as new head
{
while (head != null && head.Data == k)
head = head.Next; // skip initial nodes that equal to k
while (head != null && head.Next != null)
{
if (head.Next.Data == k)
head.Next = head.Next.Next; // delete next node
else
head = head.Next; // advance pointer
}
return head;
}
Node* Delete(Node* head, int k)
{
if (! head) return head;
while (head && head->GetValue() == k) {
Node* next = head->GetNext();
delete head;
head = next;
}
if (! head) return head;
Node* pre = head;
Node* node = head->GetNext();
while(node) {
if (node->GetValue() == k) {
Node* next = node->GetNext();
delete node;
pre->GetNext() = next;
node = next;
} else {
pre = node;
node = node->GetNext();
}
}
return head;
}
void DeleteElements(Node **head, int k)
{
if (*head == NULL) return;
Node *prevNode = *head;
Node *nextNode = NULL;
for (Node *cur = head->next; cur != NULL; cur = nextNode) {
next = cur->next;
if (cur->val == k) {
delete cur;
prevNode->next = next;
} else {
prevNode = cur;
}
}
if ((*head)->val == k)) {
Node *tmp = *head;
head = (*head)->next;
delete tmp;
}
}
void remove_node(struct link_node **head, int k)
{
struct link_node *temp;
while (*head != NULL) {
if ((*head)->data == k) {
temp = *head;
*head = (*head)->next;
} else {
head = &(*head)->next;
}
}
}
ListNode* delete(ListNode* head, int k)
{
ListNode* h = head, prev = NULL;
while (h != NULL)
{
if (h->val == k) {
if (prev == NULL) head = h->next;
if (prev) prev->next = h->next;
ListNode* tmp = h;
delete h;
}
h = h->next;
}
}
273 LIST* delete_all_occurences_recursive(LIST* node, int value) {
274
275 LIST* temp;
276
277
278 if(node && node->next == NULL)
279 return node;
280 if(!node)
281 return NULL;
282
283 temp = delete_all_occurences_recursive(node->next, value);
284 if(temp->value == value){
285 node->next = temp->next;
286 free(temp);
287 }
288 return node;
289
290
}
private void deleteAllWithK(int i) {
SLLNode head = list1.head;
SLLNode node = list1.head.next;
SLLNode prev = list1.head;
while(node != null && node != list1.head){
if(node.data == i)
{
prev.next = node.next;
System.out.println("not in head - deleting");
node = null;
}
node = node.next;
prev = prev.next;
}
if(head.data == i){
SLLNode headNode = head;
head = headNode.next;
headNode = null;
}
}
- January 18, 2011