Given a Linked List and two integers X and Y, the task is to remove all occurrences of Y after the first occurrence of a node with value X and print the modified linked list.
Examples:
Input: 7 ? 20 ? 9 ? 10 ? 20 ? 14 ? 15 ? 20, X = 10, Y = 20
Output: 7 ? 20 ? 9 ? 10 ? 14 ? 15Input: LL: 10 ? 20, X = 10, Y = 20
Output: LL: 10
Approach: The given problem can be solved by traversing the given Linked List and deleting all the nodes with value Y occurring after the node with value X. Follow the steps below to solve the problem:
- Initialize two list nodes, K and prev, to store the current head of the given Linked List and the previous node of the current head of the Linked List.
- Traverse the given Linked List until K becomes NULL and performs the following steps:
- Iterate the node K until a node with value X is found and simultaneously update the node prev as the previous node K.
- Store the node K in another variable, say temp, and traverse the Linked List until the node with value Y has occurred and simultaneously update the node prev to the previous node K.
- If the value of temp is NULL, then break out of the loop. Otherwise, update the next pointer of prev to the next pointer of temp and update temp to the next pointer of the node prev.
- After completing the above steps, print the modified Linked List.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Structure of a node// of a Linked Listclass Node {public: int data; Node* next; Node(int d) { data = d; next = NULL; }};class Solution {public: // Head of the linked list Node* head = NULL; // Function to delete all occurrences // of key after first occurrence of A void deleteKey(int A, int key) { // Stores the head node Node *k = head, *prev = NULL; while (k != NULL) { // Iterate until the // node A occurs while (k != NULL && k->data != A) { prev = k; k = k->next; } Node* temp = k; while (temp != NULL && temp->data != key) { prev = temp; temp = temp->next; } // If the entire linked // list has been traversed if (temp == NULL) return; // Update prev and temp node prev->next = temp->next; temp = prev->next; } } // Function to insert a new Node // at the front of the Linked List void push(int new_data) { // Create a new node Node* new_node = new Node(new_data); // Insert the node at the front new_node->next = head; // Update the head of LL head = new_node; } // Function to print the Linked List void printList() { Node* tnode = head; // Traverse the Linked List while (tnode != NULL) { // Print the node cout << tnode->data << " "; // Update tnode tnode = tnode->next; } }};// Update tnodeint main(){ Solution obj; obj.push(20); obj.push(15); obj.push(10); obj.push(20); obj.push(10); obj.push(9); obj.push(20); obj.push(7); int X = 10, Y = 20; obj.deleteKey(X, Y); // Print the updated list obj.printList(); return 0;}// This code is contributed by Tapesh(tapeshdua420) |
Java
// Java program for the above approachimport java.io.*;import java.util.*;import java.util.LinkedList;class Main { // Head of the linked list static Node head; // Structure of a node // of a Linked List class Node { int data; Node next; Node(int d) { data = d; next = null; } } // Function to delete all occurrences // of key after first occurrence of A void deleteKey(int A, int key) { // Stores the head node Node k = head, prev = null; while (k != null) { // Iterate until the // node A occurrs while (k != null && k.data != A) { prev = k; k = k.next; } Node temp = k; while (temp != null && temp.data != key) { prev = temp; temp = temp.next; } // If the entire linked // list has been traversed if (temp == null) return; // Update prev and temp node prev.next = temp.next; temp = prev.next; } } // Function to insert a new Node // at the front of the Linked List public void push(int new_data) { // Create a new node Node new_node = new Node(new_data); // Insert the node at the front new_node.next = head; // Update the head of LL head = new_node; } // Function to print the Linked List public void printList() { // Stores the head node Node tnode = head; // Traverse the Linked List while (tnode != null) { // Print the node System.out.print(tnode.data + " "); // Update tnode tnode = tnode.next; } } // Driver Code public static void main(String[] args) { Main list = new Main(); list.push(20); list.push(15); list.push(10); list.push(20); list.push(10); list.push(9); list.push(20); list.push(7); int X = 10; int Y = 20; list.deleteKey(X, Y); // Print the updated list list.printList(); }} |
Python3
# Python3 program for the above approach# Structure of a node# of a Linked Listclass Node: def __init__(self, x): self.data = x self.left = None self.right = None# Function to delete all occurrences# of key after first occurrence of Adef deleteKey(head, A, key): # Stores the head node k, prev = head, None while (k != None): # Iterate until the # node A occurrs while (k != None and k.data != A): prev = k k = k.next temp = k while (temp != None and temp.data != key): prev = temp temp = temp.next # If the entire linked # list has been traversed if (temp == None): return # Update prev and temp node prev.next = temp.next temp = prev.next return head# Function to insert a new Node# at the front of the Linked Listdef push(head, new_data): # Create a new node new_node = Node(new_data) # Insert the node at the front new_node.next = head # Update the head of LL head = new_node return head# Function to print the Linked Listdef printList(head): # Stores the head node tnode = head # Traverse the Linked List while (tnode.next != None): # Print the node print(tnode.data, end = " ") # Update tnode tnode = tnode.next# Driver Codeif __name__ == '__main__': list = None list = push(list, 20) list = push(list, 15) list = push(list, 10) list = push(list, 20) list = push(list, 10) list = push(list, 9) list = push(list, 20) list = push(list, 7) X = 10 Y = 20 list = deleteKey(list, X, Y) # Print the updated list printList(list)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class Node{ public int data; public Node next; public Node(int d) { data = d; next = null; }}class GFG{ // Head of the linked liststatic Node head;// Function to delete all occurrences// of key after first occurrence of Avoid deleteKey(int A, int key){ // Stores the head node Node k = head, prev = null; while (k != null) { // Iterate until the // node A occurrs while (k != null && k.data != A) { prev = k; k = k.next; } Node temp = k; while (temp != null && temp.data != key) { prev = temp; temp = temp.next; } // If the entire linked // list has been traversed if (temp == null) return; // Update prev and temp node prev.next = temp.next; temp = prev.next; }}// Function to insert a new Node// at the front of the Linked Listpublic void push(int new_data){ // Create a new node Node new_node = new Node(new_data); // Insert the node at the front new_node.next = head; // Update the head of LL head = new_node;}// Function to print the Linked Listpublic void printList(){ // Stores the head node Node tnode = head; // Traverse the Linked List while (tnode != null) { // Print the node Console.Write(tnode.data + " "); // Update tnode tnode = tnode.next; }}// Driver Codestatic public void Main(){ GFG list = new GFG(); list.push(20); list.push(15); list.push(10); list.push(20); list.push(10); list.push(9); list.push(20); list.push(7); int X = 10; int Y = 20; list.deleteKey(X, Y); // Print the updated list list.printList();}} // This code is contributed by patel2127 |
Javascript
<script> // javascript program for the above approach // Head of the linked list var head; // Structure of a node // of a Linked List class Node { constructor(val) { this.data = val; this.next = null; } } // Function to delete all occurrences // of key after first occurrence of A function deleteKey(A , key) { // Stores the head node var k = head, prev = null; while (k != null) { // Iterate until the // node A occurrs while (k != null && k.data != A) { prev = k; k = k.next; } var temp = k; while (temp != null && temp.data != key) { prev = temp; temp = temp.next; } // If the entire linked // list has been traversed if (temp == null) return; // Update prev and temp node prev.next = temp.next; temp = prev.next; } } // Function to insert a new Node // at the front of the Linked List function push(new_data) { // Create a new node var new_node = new Node(new_data); // Insert the node at the front new_node.next = head; // Update the head of LL head = new_node; } // Function to print the Linked List function printList() { // Stores the head node var tnode = head; // Traverse the Linked List while (tnode != null) { // Print the node document.write(tnode.data + " "); // Update tnode tnode = tnode.next; } } // Driver Code push(20); push(15); push(10); push(20); push(10); push(9); push(20); push(7); var X = 10; var Y = 20; deleteKey(X, Y); // Print the updated list printList();// This code is contributed by Rajput-Ji </script> |
Output:
7 20 9 10 10 15
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!
