Delete all the nodes from the list that are greater than x
Given a linked list, the problem is to delete all the nodes from the list that are greater than the specified value x.
Examples:
Input : list: 7->3->4->8->5->1 x = 6 Output : 3->4->5->1 Input : list: 1->8->7->3->7->10 x = 7 Output : 1->7->3->7
Approach: This is mainly a variation of the post which deletes first occurrence of a given key. We need to first check for all occurrences at head node which are greater than ‘x’, delete them and change the head node appropriately. Then we need to check for all occurrences inside a loop and delete them one by one.
Implementation:
CPP
// C++ implementation to delete all the nodes from the list // that are greater than the specified value x #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 greater than the specified value x void deleteGreaterNodes(Node** head_ref, int x) { Node *temp = *head_ref, *prev; // If head node itself holds the value greater than 'x' if (temp != NULL && temp->data > x) { *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 <= x) { 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 program to test above int main() { // Create list: 7->3->4->8->5->1 Node* head = getNode(7); head->next = getNode(3); head->next->next = getNode(4); head->next->next->next = getNode(8); head->next->next->next->next = getNode(5); head->next->next->next->next->next = getNode(1); int x = 6; cout << "Original List: " ; printList(head); deleteGreaterNodes(&head, x); cout << "\nModified List: " ; printList(head); return 0; } |
Java
// Java implementation to delete all nodes from the list // that are greater than the specified value x import java.io.*; class Node { int data; Node next; } class GFG { // Function to get a new node. public Node getNode( int data) { Node new_node = new Node(); new_node.data = data; new_node.next = null ; return new_node; } // Function to print linked list. public void printList(Node head) { Node temp = head; while (temp != null ) { System.out.print(temp.data + " " ); temp = temp.next; } } // Functions to delete nodes which have greater value // than x. public Node deleteGreaterNodes(Node head, int x) { Node temp = head; // while loop takes care if head node value greater // than x. while (temp != null && temp.data > x) { temp = temp.next; head = temp; // new head. } temp = head; Node prev = temp; // nodes other than head having value greater than x while (temp != null ) { while (temp != null && temp.data <= x) { prev = temp; temp = temp.next; } if (temp == null ) { return head; } // if there is a node in middle which has // greater value, we point the node to the next // node. prev.next = temp.next; // update temp for next iteration of loop. temp = prev.next; } return head; } public static void main(String[] args) { GFG list = new GFG(); // Create list: 7->3->4->8->5->1. Node head = list.getNode( 7 ); head.next = list.getNode( 3 ); head.next.next = list.getNode( 4 ); head.next.next.next = list.getNode( 8 ); head.next.next.next.next = list.getNode( 5 ); head.next.next.next.next.next = list.getNode( 1 ); System.out.print( "Original List: " ); list.printList(head); int x = 6 ; head = list.deleteGreaterNodes(head, x); System.out.print( "\nModified List: " ); list.printList(head); } } // This code is contributed by lokesh (lokeshmvs21). |
Python3
# Python program to delete all the nodes from the list # that are greater than the specified value x # structure of node class Node: def __init__( self , key): self .data = key self . next = None # function to get a new node def getNode(data): return Node(data) # function to delete all the nodes from the list # that are greater than the specified value x def deleteGreaterNodes(head_ref, x): temp = head_ref prev = None # if head node itself holds the value greater than 'x' while (temp is not None and temp.data > x): 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 < = x): 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 list def printList(head): while (head is not None ): print (head.data, end = " " ) head = head. next print ( "\n" ) # driver code to test above functions head = getNode( 7 ) head. next = getNode( 3 ) head. next . next = getNode( 4 ) head. next . next . next = getNode( 8 ) head. next . next . next . next = getNode( 5 ) head. next . next . next . next . next = getNode( 1 ) x = 6 print ( "Original List: " ) printList(head) head = deleteGreaterNodes(head, x) print ( "Modified List: " ) printList(head) # THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
C#
using System; // Structure of a node public class Node { public int Data; public Node Next; public Node( int data) { Data = data; Next = null ; } } public class LinkedList { // Function to delete all nodes from the list that are greater than the specified value x public static void DeleteGreaterNodes( ref Node head, int x) { Node temp = head; Node prev = null ; // If the head node itself holds a value greater than 'x' if (temp != null && temp.Data > x) { head = temp.Next; // Change the head temp = null ; // Free old head temp = head; // Change temp } // Delete occurrences other than the 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 <= x) { prev = temp; temp = temp.Next; } // If the required value node was not present in the linked list if (temp == null ) return ; // Unlink the node from the linked list prev.Next = temp.Next; temp = null ; // Free memory // Update Temp for the next iteration of the outer loop temp = prev.Next; } } // Function to print a linked list public static void PrintList(Node head) { while (head != null ) { Console.Write(head.Data + " " ); head = head.Next; } } // Driver program to test the above methods public static void Main( string [] args) { // Create list: 7->3->4->8->5->1 Node head = new Node(7); head.Next = new Node(3); head.Next.Next = new Node(4); head.Next.Next.Next = new Node(8); head.Next.Next.Next.Next = new Node(5); head.Next.Next.Next.Next.Next = new Node(1); int x = 6; Console.Write( "Original List: " ); PrintList(head); DeleteGreaterNodes( ref head, x); Console.Write( "\nModified List: " ); PrintList(head); } } // This code is contributed by shivamgupta0987654321 |
Javascript
// JavaScript implementation to delete all the nodes from the list // that are greater than the specified value x // structure of a node class Node{ constructor(data){ this .data = data; this .next = null ; } } // function to get a new Node function getNode(data){ let newNode = new Node(data); return newNode; } // function to delete all the nodes from the list // that are greater than the specified value x function deleteGreaterNodes(head_ref, x){ let temp = head_ref; let prev; // If head node itself holds the value greater than 'x' if (temp != null && temp.data > x){ 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 <= x){ prev = temp; temp = temp.next; } // If required value node 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 function printList(head){ while (head != null ){ console.log(head.data + " " ); head = head.next; } } // Driver code to test above functions // create list: 7->3->4->8->5->1 let head = getNode(7); head.next = getNode(3); head.next.next = getNode(4); head.next.next.next = getNode(8); head.next.next.next.next = getNode(5); head.next.next.next.next.next = getNode(1); let x = 6; console.log( "Original List:" ); printList(head); head = deleteGreaterNodes(head, x); console.log( "Modified List:" ); printList(head); // This code is contributed by Kirti Agarwal |
Original List: 7 3 4 8 5 1 Modified List: 3 4 5 1
Time Complexity: O(n).
Using Recursion:
The idea is to traverse the linked list recursively and delete all nodes whose value is greater than x. We start the traversal from the head of the linked list and move to the next node until we reach the end of the list.
- Check if the head of the linked list is NULL. If it is, return NULL.
- Recursively traverse the sub-list starting from head’s next pointer and delete all nodes greater than x.
- Check if head’s value is greater than x. If it is, delete the node and return its next pointer to the previous level of the recursion.
- Otherwise, simply return the node itself.
- Repeat steps 2-4 for all nodes in the linked list.
- Return the head of the modified linked list.
Below is the implementation of the above approach:
C++
// C++ code to implement recursive approach #include <iostream> using namespace std; // Definition of a linked list node class Node { public : int data; Node* next; Node( int value) { data = value; next = NULL; } }; // Function to delete nodes greater than x using recursion Node* deleteGreaterNodes(Node* head, int x) { if (head == NULL) { return NULL; } head->next = deleteGreaterNodes( head->next, x); // Recursively delete all nodes // greater than x in the sub-list // starting from head's next pointer if (head->data > x) { // If head's value is greater than x, delete // head and return its next pointer Node* temp = head->next; delete head; return temp; } return head; // Otherwise, return head } // Function to print the linked list void printList(Node* head) { while (head != NULL) { cout << head->data << " " ; head = head->next; } cout << endl; } // Driver code int main() { // Create a linked list: 7->3->4->8->5->1 Node* head = new Node(7); head->next = new Node(3); head->next->next = new Node(4); head->next->next->next = new Node(8); head->next->next->next->next = new Node(5); head->next->next->next->next->next = new Node(1); int x = 6; cout << "Original List: " ; printList(head); // Delete nodes greater than x head = deleteGreaterNodes(head, x); cout << "List after deleting nodes greater than " << x << ": " ; printList(head); return 0; } // This code is contributed by Veerendra_Singh_Rajpoot |
Java
// Definition of a linked list node class Node { int data; Node next; Node( int value) { data = value; next = null ; } } public class Main { // Function to delete nodes greater than x using recursion static Node deleteGreaterNodes(Node head, int x) { if (head == null ) { return null ; } head.next = deleteGreaterNodes( head.next, x); // Recursively delete all nodes // greater than x in the sub-list // starting from head's next pointer if (head.data > x) { // If head's value is greater than x, delete // head and return its next pointer Node temp = head.next; head = null ; // Delete the node return temp; } return head; // Otherwise, return head } // Function to print the linked list static void printList(Node head) { while (head != null ) { System.out.print(head.data + " " ); head = head.next; } System.out.println(); } // Driver code public static void main(String[] args) { // Create a linked list: 7->3->4->8->5->1 Node head = new Node( 7 ); head.next = new Node( 3 ); head.next.next = new Node( 4 ); head.next.next.next = new Node( 8 ); head.next.next.next.next = new Node( 5 ); head.next.next.next.next.next = new Node( 1 ); int x = 6 ; System.out.print( "Original List: " ); printList(head); // Delete nodes greater than x head = deleteGreaterNodes(head, x); System.out.print( "List after deleting nodes greater than " + x + ": " ); printList(head); } } |
Python3
# Python code to implement recursive approach # Definition of a linked list node class Node: def __init__( self , value): self .data = value self . next = None # Function to delete nodes greater than x using recursion def deleteGreaterNodes(head, x): if head is None : return None head. next = deleteGreaterNodes(head. next , x) # Recursively delete all nodes # greater than x in the sub-list # starting from head's next pointer if head.data > x: # If head's value is greater than x, delete # head and return its next pointer temp = head. next del head return temp return head # Otherwise, return head # Function to print the linked list def printList(head): while head is not None : print (head.data, end = " " ) head = head. next print () # Driver code if __name__ = = "__main__" : # Create a linked list: 7->3->4->8->5->1 head = Node( 7 ) head. next = Node( 3 ) head. next . next = Node( 4 ) head. next . next . next = Node( 8 ) head. next . next . next . next = Node( 5 ) head. next . next . next . next . next = Node( 1 ) x = 6 print ( "Original List: " , end = "") printList(head) # Delete nodes greater than x head = deleteGreaterNodes(head, x) print (f "List after deleting nodes greater than {x}: " , end = "") printList(head) # This code is contributed by Susobhan Akhuli |
C#
using System; // Definition of a linked list node public class Node { public int data; public Node next; public Node( int value) { data = value; next = null ; } } public class GFG { // Function to delete nodes greater than x using recursion public static Node DeleteGreaterNodes(Node head, int x) { if (head == null ) { return null ; } head.next = DeleteGreaterNodes(head.next, x); // Recursively delete all nodes // greater than x in the sub-list // starting from head's next pointer if (head.data > x) // If head's value is greater than x, delete // head and return its next pointer { Node temp = head.next; head.next = null ; return temp; } return head; // Otherwise, return head } // Function to print the linked list public static void PrintList(Node head) { while (head != null ) { Console.Write(head.data + " " ); head = head.next; } Console.WriteLine(); } public static void Main() { // Create a linked list: 7->3->4->8->5->1 Node head = new Node(7); head.next = new Node(3); head.next.next = new Node(4); head.next.next.next = new Node(8); head.next.next.next.next = new Node(5); head.next.next.next.next.next = new Node(1); int x = 6; Console.Write( "Original List: " ); PrintList(head); // Delete nodes greater than x head = DeleteGreaterNodes(head, x); Console.Write( "List after deleting nodes greater than " + x + ": " ); PrintList(head); } } |
Javascript
// Definition of a linked list node class Node { constructor(value) { this .data = value; this .next = null ; } } // Function to delete nodes greater than x using recursion function deleteGreaterNodes(head, x) { if (head === null ) { return null ; } head.next = deleteGreaterNodes(head.next, x); // Recursively delete all nodes // greater than x in the sub-list // starting from head's next pointer if (head.data > x) { // If head's value is greater than x, delete head const temp = head.next; head = null ; // Free memory by setting head to null return temp; // Return its next pointer } return head; // Otherwise, return head } // Function to print the linked list function printList(head) { let current = head; while (current !== null ) { console.log(current.data + " " ); current = current.next; } console.log(); } // Driver code // Create a linked list: 7->3->4->8->5->1 const head = new Node(7); head.next = new Node(3); head.next.next = new Node(4); head.next.next.next = new Node(8); head.next.next.next.next = new Node(5); head.next.next.next.next.next = new Node(1); const x = 6; console.log( "Original List: " ); printList(head); // Delete nodes greater than x const newHead = deleteGreaterNodes(head, x); console.log( "List after deleting nodes greater than " + x + ": " ); printList(newHead); |
Original List: 7 3 4 8 5 1 List after deleting nodes greater than 6: 3 4 5 1
Time Complexity: O(n) where n is the number of nodes in the linked list.
Auxiliary Space: O(n), due to the recursive call stack.
Contact Us