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 approachÂ
import 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!
