Delete all Occurrence of the key from the given linked list

Delete all Occurrence of the key from the given linked list” is again one of the important problem asked in many technical interview based on linked list. Here, we are given a linked list and our task is to delete all occurrences of a given key ‘x’ from a linked list.

For example, we need to delete all occurrences of ‘45’ from a given list.
List:   45 -> 55 -> 32 -> 45 -> 66 -> 71 -> 45 -> 33 -> 45
After deleting all occurrences of ‘45’, the list will become:
List:   55 -> 32 -> 66 -> 71 -> 33

The steps required to delete all occurrences of a given key from a linked list is as follows:

  1. Before traversing the complete linked list, we will delete all beginning occurrences of given key ‘x’ and adjust our head accordingly.
  2. Now, after adjusting the head of the linked list, we will traverse the complete linked list and delete all occurrences of given key ‘x’ from a linked list.

C++ Program to delete all occurrences of a given key from a linked list is as follows:

/* C++ Program to delete all occurrences of the given key from the Linked List */
#include<bits/stdc++.h>
using namespace std;

/* Structure of the node of the linked list */
typedef struct node
{
    int data;
    struct node *next;
}Node;

/* Function to Insert node at the end of the linked list */
void insert_end(Node **head, int ele)
{
    /* Creating a new node */
    Node *new_node;
    new_node = (struct node*)malloc(sizeof(struct node));
    new_node->data = ele;
    new_node->next = NULL;
    
    /* check whether the linked list is empty or not */
    
    /* If Linked List is empty, then new node will become head of the linked list */
    if(*head == NULL)     
    {
        *head = new_node;
        return;
    }
    
    /* If Linked List is not empty, then traverse the complete linked list and point the pointer
    of last node of the linked list to the new node */
    Node *temp = NULL;
    temp = (*head);
    while(temp->next != NULL)
    temp=temp->next;
    temp->next = new_node;
}

/* Function to delete all occurrences of a given key from a linked list */
Node *deleteAllx(Node *head , int x)
{
    /* If Linked List is empty, return head */
    if(head == NULL)
        return head; 
    
    /* Delete All occurrences of the given key from the beginning, and adjust head accordingly */
    while(head!=NULL && head->data==x)
        head=head->next;
        
    /* Now, delete remaining occurrences of the key from the linked list by storing the previous 
    node and pointing it to desired location accordingly */
    Node* temp=head;
    while(temp->next != NULL)
    {
        if(temp->next->data == x)
        {
            Node *p = temp->next;
            temp->next=temp->next->next;
            delete p;
        }
        else
        {
            temp=temp->next;
        }
    }
    return head;
}

/* Function to Print the Linked List  */
void print(Node *head)
{
    Node *temp = head;
    while(temp!=NULL)
    {
        cout<<temp->data<<" ";
        temp=temp->next;
    }
    cout<<endl;
}
int main()
{
    Node *head;
    head = NULL;
    /* Inserting Some Nodes in the Linked List */
    insert_end(&head,45);
    insert_end(&head,78);
    insert_end(&head,45);
    insert_end(&head,93);
    insert_end(&head,45);
    insert_end(&head,99);
    insert_end(&head,45);
    cout<<"Linked List before deleting all occurrences of 45:\n";
    print(head);
    head = deleteAllx(head,45);
    cout<<"\nLinked List after deleting all occurrences of 45:\n";
    print(head);
}
OUTPUT:
Linked List before deleting all occurrences of 45:
45 78 45 93 45 99 45
Linked List after deleting all occurrences of 45:
78 93 99

Related Posts:

  1. Delete Complete Linked List.
  2. Delete Nth Node of the Linked List.
  3. Delete without head pointer of the Linked List.
  4. Delete Alternate Nodes of the Linked List.
  5. Delete every ‘N’ Nodes After ‘M’ Nodes of the Linked List.
  6. Remove Duplicate Nodes from an Unsorted Linked List.
  7. Remove Duplicate Nodes from a Sorted Linked List.
  8. Find Union and Intersection of Two Linked List.
  9. Merge Two Sorted Linked List.
  10. Insert a New Node at the Sorted Linked List.
  11. Reverse a Linked List.
  12. Reverse a Linked List Using Stack.
  13. Printing Linked List in Reverse Order without actually reversing the Linked List.
  14. Swap Adjacent Elements of the Linked List.
  15. Count All Occurrences of a Particular Node in a Linked List.
  16. Bubble Sort on Linked List.
  17. Detect a Loop in a Linked List.
  18. Find the Length of the Loop present in the Linked List.
  19. Detect and Remove Loop from a Linked List.
  20. Segregate Even and Odd Nodes of the Linked List.

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *