Delete all occurrences of a given key in a linked list ?
- Given a singly linked list, delete all occurrences of a given key in it. For example,
Input: 2 -> 1 -> 8 -> 2 -> 3 -> 2 -> 7
Key to delete = 2
Output: 1 -> 8 -> 3 -> 7
Sample Code in C
#include <stdio.h>
#include <stdlib.h>
// A linked list node
struct Node
{
int data;
struct Node *next;
};
/* Given a reference (pointer to pointer) to the head of a list
and an int, inserts a new node on the front of the list. */
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* Given a reference (pointer to pointer) to the head of a list and
a key, deletes all occurrence of the given key in linked list */
void deleteKey(struct Node **head_ref, int key)
{
// Store head node
struct Node* temp = *head_ref, *prev;
// If head node itself holds the key or multiple occurrences of key
while (temp != NULL && temp->data == key)
{
*head_ref = temp->next; // Changed head
free(temp); // free old head
temp = *head_ref; // Change Temp
}
// Delete occurrences other than head
while (temp != NULL)
{
// Search for the key to be deleted, keep track of the
// previous node as we need to change 'prev->next'
while (temp != NULL && temp->data != key)
{
prev = temp;
temp = temp->next;
}
// If key was not present in linked list
if (temp == NULL) return;
// Unlink the node from linked list
prev->next = temp->next;
free(temp); // Free memory
//Update Temp for next iteration of outer loop
temp = prev->next;
}
}
// This function prints contents of linked list starting from
// the given node
void printList(struct Node *node)
{
while (node != NULL)
{
printf(" %d ", node->data);
node = node->next;
}
}
/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
push(&head, 7);
push(&head, 2);
push(&head, 3);
push(&head, 2);
push(&head, 8);
push(&head, 1);
push(&head, 2);
push(&head, 2);
int key = 2; // key to delete
puts("Created Linked List: ");
printList(head);
deleteKey(&head, key);
puts("\nLinked List after Deletion: ");
printList(head);
return 0;
}
Output
Categorized in:
Tagged in:
Accenture interview questions and answers, Altimetrik India Pvt Ltd interview questions and answers, Applied Materials interview questions and answers, Bharti Airtel interview questions and answers, BMC Software interview questions and answers, c program to delete first node in linked list, Capgemini interview questions and answers, CASTING NETWORKS INDIA PVT LIMITED interview questions and answers, CGI Group Inc interview questions and answers, Chetu interview questions and answers, Ciena Corporation interview questions and answers, Collabera Te interview questions and answers, delete a specific node in linked list java, delete all nodes in doubly linked list c++, delete at position in a doubly linked list, delete first node in linked list c++, delete last node in doubly linked list in c++, delete last node in linked list c++, delete last node in linked list in c, delete node at given position in a linked list in c++, delete node from doubly linked list java, Dell International Services India Pvt Ltd interview questions and answers, doubly linked list geeksforgeeks, Flipkart interview questions and answers, Genpact interview questions and answers, Globallogic India Pvt Ltd interview questions and answers, IBM interview questions and answers, Indecomm Global Services interview questions and answers, Mphasis interview questions and answers, NetApp interview questions and answers, Oracle Corporation interview questions and answers, remove element from doubly linked list c++, samsung interview questions and answers, SAP Labs India Pvt Ltd interview questions and answers, Sapient Consulting Pvt Ltd interview questions and answers, Tech Mahindra interview questions and answers, Tracxn Technologies Pvt Ltd interview questions and answers, UnitedHealth Group interview questions and answers, Wipro Infotech interview questions and answers, WM Global Technology Services India Pvt.Ltd Limited (WMGTS) interview questions and answers, write a program to delete a node from linked list in c++, write ac program to delete a particular element in the doubly linked list, write an algorithm to delete duplicate elements in a singly linked list, Xoriant Solutions Pvt Ltd interview questions and answers, Yodlee Infotech Pvt Ltd interview questions and answers