Given a Linked List and a key K. The task is to write a program to delete all the nodes from the list that are lesser than the key K.
Examples:
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
Approach: The approach is similar to deleting all nodes from the list which are greater than the given key.
There are two possible cases:
- Head node holds a value less than K: First check for all occurrences at head node which are lesser than ‘K’, delete them and change the head node appropriately.
- Some intermediate node holds value less than k: Start traversing from head and check if current node’s value is less than K. If yes then delete that node and move forward in the list.
Below is the implementation of the above approach:
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 nodestruct Node { int data; Node* next;};// function to get a new nodeNode* 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 Kvoid 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 listvoid printList(Node* head){ while (head) { cout << head->data << " "; head = head->next; }}// Driver codeint 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;} |
Java
/*package whatever //do not write package name here */import java.io.*;// Java program to delete all the nodes from the list// that are lesser than the specified value k// structure of a nodeclass Node{ int data; Node next; public Node(int data){ this.data = data; this.next = null; }}public class GFG { // function to delete all the nodes from the list // that are lesser than the specified value k public static Node deleteLesserNodes(Node head_ref, int K){ Node temp = head_ref; Node prev = null; // If head node itself holds the value lesser than 'K' while(temp != null && temp.data < K){ head_ref = temp.next; // changed 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 nodes was not present // in linked list if(temp == null) return head_ref; // unlink the node from linked list prev.next = temp.next; // Update temp for next iteration of // outer loop temp = prev.next; } return head_ref; } // function to a print a linked list public static void printList(Node head){ while(head != null){ System.out.print(head.data + " "); head = head.next; } } // Driver code public static void main(String[] args) { Node head = new Node(12); head.next = new Node(15); head.next.next = new Node(9); head.next.next.next = new Node(11); head.next.next.next.next = new Node(5); head.next.next.next.next.next = new Node(6); int K = 9; System.out.println("Initial List:"); printList(head); head = deleteLesserNodes(head, K); System.out.println("\nFinal List:"); printList(head); }}// The code is contributed by Arushi goel. |
Python3
# Python program to delete all the nodes from the list# that are lesser than the specified value K# structure of nodeclass Node: def __init__(self, key): self.data = key self.next = None # function to get a new nodedef getNode(data): return Node(data)# function to delete all the nodes from the list# that are lesser than the specified value kdef deleteLesserNodes(head_ref, K): temp = head_ref prev = None # if head node itself holds the value lesser than 'K' while(temp is not None and temp.data < K): head_ref = temp.next #changed head temp = head_ref # change temp # delete occurrences other than head while(temp is not None): # search for the node to be deleted # keep track of the previous node as we # need to change prev.next while(temp is not None and temp.data >= K): prev = temp temp = temp.next # if required value nodes was not present # in linked list if(temp is None): return head_ref # unlink the node from linked list prev.next = temp.next # update temp for next iteration of # outer loop temp = prev.next return head_ref# function to print a linked listdef printList(head): while(head is not None): print(head.data, end=" ") head = head.next print("\n")# driver code to test above functionshead = 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)K = 9print("Initial List: ")printList(head)head = deleteLesserNodes(head, K)print("Final List: ")printList(head)# THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
C#
using System;// structure of a nodeclass Node{ public int data; public Node next; public Node(int data) { this.data = data; next = null; }}class LinkedList{ // function to delete all the nodes from the list // that are lesser than the specified value K public static void DeleteLesserNodes(ref Node head_ref, int K) { Node temp = head_ref, prev = null; // If head node itself holds the value lesser than 'K' while (temp != null && temp.data < K) { head_ref = temp.next; // Changed 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; // Free memory temp = temp.next; } } // function to a print a linked list public static void PrintList(Node head) { while (head != null) { Console.Write(head.data + " "); head = head.next; } } // Driver code public static void Main() { // Create list: 12->15->9->11->5->6 Node head = new Node(12); head.next = new Node(15); head.next.next = new Node(9); head.next.next.next = new Node(11); head.next.next.next.next = new Node(5); head.next.next.next.next.next = new Node(6); int K = 9; Console.Write("Initial List: "); PrintList(head); DeleteLesserNodes(ref head, K); Console.Write("\nFinal List: "); PrintList(head); }} |
Javascript
// JavaScript Program to delete all the nodes from the list// that are lesser than then specified value k// structure of a nodeclass Node{ constructor(data){ this.data = data; this.next = null; }}// function to get a new nodefunction getNode(data){ let newNode = new Node(data); return newNode;}// function to delete all the nodes from the list// that are lesser than the specified value kfunction deleteLesserNodes(head_ref, K){ let temp = head_ref; let prev; // If head node itself holds the value lesser than 'K' while(temp != null && temp.data < K){ head_ref = temp.next; // changed 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 nodes was not present // in linked list if(temp == null) return head_ref; // unlink the node from linked list prev.next = temp.next; // Update temp for next iteration of // outer loop temp = prev.next; } return head_ref;}// function to a print a linked listfunction printList(head){ while(head != null){ console.log(head.data + " "); head = head.next; }}// Driver codelet 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);let K = 9;console.log("Initial List:");printList(head);head = deleteLesserNodes(head, K);console.log("Final List:");printList(head);// This code is contributed by Kirti Agarwal |
Output:
Initial List: 12 15 9 11 5 6 Final List: 12 15 9 11
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
