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)