Dada una Lista Enlazada y una clave K. La tarea es escribir un programa para borrar todos los Nodes de la lista que son menores que la clave K.
Ejemplos:
Input :12->15->9->11->5->6
K = 9
Output : 12 -> 15 -> 9 -> 11
Input : 13->4->16->9->22->45->5->16->6
K = 10
Output : 13 -> 16 -> 22 -> 45 -> 16
Enfoque: el enfoque es similar a eliminar todos los Nodes de la lista que son mayores que la clave dada .
Hay dos casos posibles:
- El Node principal tiene un valor menor que K: primero verifique todas las ocurrencias en el Node principal que sean menores que ‘K’, elimínelas y cambie el Node principal según corresponda.
- Algún Node intermedio tiene un valor inferior a k: Comience a atravesar desde la cabeza y compruebe si el valor del Node actual es inferior a K. En caso afirmativo, elimine ese Node y avance en la lista.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to delete all the nodes from the list
// that are lesser than the specified value K
#include <bits/stdc++.h>
using namespace std;
// structure of a node
struct Node {
int data;
Node* next;
};
// function to get a new node
Node* getNode(int data)
{
Node* newNode = new Node;
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// function to delete all the nodes from the list
// that are lesser than the specified value K
void deleteLesserNodes(Node** head_ref, int K)
{
Node *temp = *head_ref, *prev;
// If head node itself holds the value lesser than 'K'
while (temp != NULL && temp->data < K) {
*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 node to be deleted,
// keep track of the previous node as we
// need to change 'prev->next'
while (temp != NULL && temp->data >= K) {
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; // Free memory
// Update Temp for next iteration of
// outer loop
temp = prev->next;
}
}
// function to a print a linked list
void printList(Node* head)
{
while (head) {
cout << head->data << " ";
head = head->next;
}
}
// Driver code
int main()
{
// Create list: 12->15->9->11->5->6
Node* head = getNode(12);
head->next = getNode(15);
head->next->next = getNode(9);
head->next->next->next = getNode(11);
head->next->next->next->next = getNode(5);
head->next->next->next->next->next = getNode(6);
int K = 9;
cout << "Initial List: ";
printList(head);
deleteLesserNodes(&head, K);
cout << "\nFinal List: ";
printList(head);
return 0;
}
Producción:
Initial List: 12 15 9 11 5 6 Final List: 12 15 9 11
Complejidad de tiempo: O(N)