- Delete all the occurrence of a given key
- Delete all the nodes that is greater than the given key
Solution in C++
#include<iostream>
#include<vector>
#include<string>
using namespace std;
struct Node
{
int data;
Node *next;
Node(int x)
{
data = x;
next = NULL;
}
};
void print_list(Node *head)
{
Node *start = head;
while(start)
{
cout<<start->data<<" -> ";
start = start->next;
}
cout<<"\n";
}
void delete_all_occurrences_of_a_given_key(Node **head, int key)
{
Node *temp = *head, *prev;
// If head node itself holds the key or multiple occurrences of key
while (temp != NULL && temp->data == key)
{
*head = temp->next; // Changed head
free(temp); // free old head
temp = *head; // 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;
}
}
void delete_all_elements_greater_than_given_key(Node** head, int key)
{
Node *temp = *head, *prev;
// If head node itself holds the value greater than 'key'
while (temp != NULL && temp->data > key)
{
*head = temp->next; // Changed head
free(temp); // free old head
temp = *head; // Change temp
}
// Delete occurrences other than head
while (temp != NULL) {
// Search for the node 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 required value node was not present
// in linked list
if (temp == NULL)
return;
// Unlink the node from linked list
prev->next = temp->next;
delete temp;
// Update Temp for next iteration of
temp = prev->next;
}
}
int main()
{
Node *head = new Node(2);
head -> next = new Node(1);
head -> next -> next = new Node(4);
head -> next -> next -> next = new Node(3);
head -> next -> next -> next -> next = new Node(6);
head -> next -> next -> next -> next -> next = new Node(5);
cout<<"The original list = "<<endl;
print_list(head);
int key = 3;
delete_all_occurrences_of_a_given_key (&head, key );
cout<<"The list after deleting "<< key <<" key is = "<<endl;
print_list(head);
delete_all_elements_greater_than_given_key (&head, key );
cout<<"The list after deleting the elements greater than "<< key <<" key is = "<<endl;
print_list(head);
return 0;
}
List Of Tutorials available in this website: