Dada una lista enlazada y dos enteros X e Y , la tarea es eliminar todas las apariciones de Y después de la primera aparición de un Node con valor X e imprimir la lista enlazada modificada .
Ejemplos:
Entrada: 7 → 20 → 9 → 10 → 20 → 14 → 15 → 20, X = 10, Y = 20
Salida: 7 → 20 → 9 → 10 → 14 → 15Entrada: LL: 10 → 20, X = 10, Y = 20
Salida: LL: 10
Enfoque: el problema dado se puede resolver recorriendo la lista enlazada dada y eliminando todos los Nodes con el valor Y que aparecen después del Node con el valor X. Siga los pasos a continuación para resolver el problema:
- Inicialice dos Nodes de lista, K y prev , para almacenar el encabezado actual de la Lista vinculada dada y el Node anterior del encabezado actual de la Lista vinculada.
- Recorra la lista enlazada dada hasta que K se convierta en NULL y realice los siguientes pasos:
- Iterar el Node K hasta que se encuentre un Node con valor X y actualizar simultáneamente el Node anterior como el Node anterior K .
- Almacene el Node K en otra variable, digamos temp , y recorra la lista enlazada hasta que aparezca el Node con el valor Y y actualice simultáneamente el Node anterior al Node anterior K .
- Si el valor de temp es NULL , salga del bucle . De lo contrario, actualice el siguiente puntero de prev al siguiente puntero de temp y actualice temp al siguiente puntero del Node prev .
- Después de completar los pasos anteriores, imprima la Lista vinculada modificada .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a node
// of a Linked List
class 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 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
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 tnode
int 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 List class 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 A def 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 List def 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 List def 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 Code if __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 approach
using System;
class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
class GFG{
// Head of the linked list
static Node head;
// 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
Console.Write(tnode.data + " ");
// Update tnode
tnode = tnode.next;
}
}
// Driver Code
static 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>
Producción:
7 20 9 10 10 15
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por dixitashish628 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA