Eliminar todos los Nodes de la lista que son menores que K

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: 

  1. 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.
  2. 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)
 

Publicación traducida automáticamente

Artículo escrito por Rajput-Ji y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *