Dada una lista enlazada individualmente que contiene N Nodes, la tarea es eliminar todos los Nodes pares de la lista.
Ejemplos:
Entrada: LL = 1 -> 4 -> 3 -> 18 -> 19
Salida: 1 -> 3 -> 19
Entrada: LL = 5 -> 3 -> 6 -> 8 -> 4 -> 1 -> 2 – > 9
Salida: 5 -> 3 -> 1 -> 9
Enfoque 1:
- La idea es atravesar los Nodes de la lista enlazada individualmente uno por uno y obtener el puntero de los Nodes que tienen datos pares. Elimine esos Nodes siguiendo el enfoque utilizado en esta publicación.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ implementation to delete all
// even nodes from the singly linked list
#include <bits/stdc++.h>
using namespace std;
// Node of the singly linked list
struct Node
{
int data;
struct Node* next;
};
// Function to insert a node at
// the beginning of the singly
// Linked List
void push(struct Node** head_ref,
int new_data)
{
struct Node* new_node
= (struct Node*)malloc(
sizeof(
struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
// Function to delete a node in a
// singly Linked List.
// head_ref --> Pointer to head
// node pointer.
// key --> Node to be deleted
void deleteNode(struct Node** head_ref,
int key)
{
// Store head node
struct Node *temp = *head_ref,
*prev;
// If head node itself holds
// the key to be deleted
if (temp != NULL
&& temp->data == key) {
// Changed head
*head_ref = temp->next;
return;
}
// Search for the key to be
// deleted, keep track of the
// previous node as we need
// to change 'prev->next'
while (temp != NULL
&& temp->data != key) {
prev = temp;
temp = temp->next;
}
// If key was not present
// in linked list
if (temp == NULL)
return;
// Unlink the node from
// linked list
prev->next = temp->next;
}
// Function to delete all the
// even nodes from the
// singly linked list
void deleteEvenNodes(Node** head_ref)
{
Node* ptr = *head_ref;
// Node* next;
while (ptr != NULL) {
// next = ptr->next;
// If true, delete node 'ptr'
if (ptr->data % 2 == 0)
deleteNode(head_ref,
ptr->data);
ptr = ptr->next;
}
}
// This function prints contents
// of linked list starting from
// the given node
void printList(struct Node* node)
{
while (node != NULL) {
printf(" %d -> ", node->data);
node = node->next;
}
}
// Driver code
int main()
{
// Start with the empty list
Node* head = NULL;
push(&head, 19);
push(&head, 18);
push(&head, 3);
push(&head, 4);
push(&head, 1);
printf("Initial List: ");
printList(head);
deleteEvenNodes(&head);
printf("\nFinal List: ");
printList(head);
}
Java
// Java implementation to delete all
// even nodes from the singly linked list
class LinkedList{
// head of list
Node head;
// Linked list Node
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
// Function to insert a node at
// the beginning of the singly
// Linked List
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
// Function to delete a node in a
// singly Linked List.
void deleteNode(int key)
{
// Store head node
Node temp = head, prev = null;
// If head node itself holds the
// key to be deleted
if (temp != null && temp.data == key)
{
// Changed head
head = temp.next;
return;
}
// Search for the key to be deleted,
// keep track of the previous node
// as we need to change temp.next
while (temp != null && temp.data != key)
{
prev = temp;
temp = temp.next;
}
// If key was not present in linked list
if (temp == null) return;
// Unlink the node from linked list
prev.next = temp.next;
}
// Function to delete all the nodes
// from linked list containing
// even numbers.
void deleteEvenNodes()
{
Node ptr = head;
// loop to iterate the linked list
while(ptr != null)
{
// If containing element is even
if(ptr.data % 2 == 0)
{
// Delete the node
deleteNode(ptr.data);
}
ptr = ptr.next;
}
}
// This function prints contents of linked
// list starting from the given node
public void printList()
{
Node ptr = head;
while (ptr != null)
{
System.out.print(ptr.data + "-> ");
ptr = ptr.next;
}
}
// Driver code
public static void main(String[] args)
{
LinkedList head = new LinkedList();
head.push(19);
head.push(18);
head.push(3);
head.push(4);
head.push(1);
System.out.print("\nInitial List: ");
head.printList();
head.deleteEvenNodes();
System.out.print("\nFinal List: ");
head.printList();
}
}
// This code is contributed by Amit Mangal
Python3
# Python3 implementation to delete all
# even nodes from the singly linked list
# Node class
class Node:
# Function to initialize the node object
def __init__(self, data):
# Assign data
self.data = data
# Initialize
# next as null
self.next = None
# Linked List Class
class LinkedList:
# Function to initialize the
# LinkedList class.
def __init__(self):
# Initialize head as None
self.head = None
# This function insert a new node at
# the beginning of the linked list
def push(self, new_data):
# Create a new Node
new_node = Node(new_data)
# Make next of new Node as head
new_node.next = self.head
# Move the head to point to new Node
self.head = new_node
# Method to print the linked list
def printList(self):
# Object to iterate
# the list
ptr = self.head
# Loop to iterate list
while(ptr != None):
print(ptr.data, '-> ', end = '')
# Moving the iterating object
# to next node
ptr = ptr.next
print()
# Method to delete a node in
# a singly linked list.
def deleteNode(self, key):
temp = self.head
# If head node itself holds
# the key to be deleted.
if(temp != None and temp.data == key):
# Changing head of list.
self.head = temp.next
return
# Search for the key to be
# deleted, keep track of the
# previous node as we need
# to change prev.next
while(temp != None and temp.data != key):
prev = temp
temp = temp.next
# If is not present in list
if(temp == None):
return
# Unlink the node from
# linked list
prev.next = temp.next
# Method to delete all the
# even nodes from singly
# linked list.
def deleteEvenNodes(self):
ptr = self.head
# Loop to iterate the
# linked list.
while(ptr != None):
# If node contains even number.
if(ptr.data % 2 == 0):
# Deleting the node
self.deleteNode(ptr.data)
ptr = ptr.next
# Driver code
if __name__=='__main__':
head = LinkedList()
# Pushing elements at start
# of linked list.
head.push(19)
head.push(18)
head.push(3)
head.push(4)
head.push(1)
# Print initial linked list
print("Initial list: ", end = '')
head.printList()
# Calling the function to delete
# nodes containing even numbers.
head.deleteEvenNodes()
# Print the final list
print("Final list: ", end = '')
head.printList()
# This code is contributed by Amit Mangal
C#
// C# implementation to delete all
// even nodes from the singly linked list
using System;
class List{
// head of list
Node head;
// Linked list Node
public class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
// Function to insert a node at
// the beginning of the singly
// Linked List
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
// Function to delete a node in a
// singly Linked List.
void deleteNode(int key)
{
// Store head node
Node temp = head, prev = null;
// If head node itself holds the
// key to be deleted
if (temp != null &&
temp.data == key)
{
// Changed head
head = temp.next;
return;
}
// Search for the key to be deleted,
// keep track of the previous node
// as we need to change temp.next
while (temp != null &&
temp.data != key)
{
prev = temp;
temp = temp.next;
}
// If key was not present
// in linked list
if (temp == null)
return;
// Unlink the node from
// linked list
prev.next = temp.next;
}
// Function to delete
// all the nodes from
// linked list containing
// even numbers.
void deleteEvenNodes()
{
Node ptr = head;
// loop to iterate the linked list
while(ptr != null)
{
// If containing element is even
if(ptr.data % 2 == 0)
{
// Delete the node
deleteNode(ptr.data);
}
ptr = ptr.next;
}
}
// This function prints contents of linked
// list starting from the given node
public void printList()
{
Node ptr = head;
while (ptr != null)
{
Console.Write(ptr.data + "-> ");
ptr = ptr.next;
}
}
// Driver code
public static void Main(String []args)
{
List head = new List();
head.push(19);
head.push(18);
head.push(3);
head.push(4);
head.push(1);
Console.Write("\nInitial List: ");
head.printList();
head.deleteEvenNodes();
Console.Write("\nFinal List: ");
head.printList();
}
}
// This code contributed by gauravrajput1
Javascript
<script>
// javascript implementation to delete all
// even nodes from the singly linked list
// head of list
var head;
// Linked list Node
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
// Function to insert a node at
// the beginning of the singly
// Linked List
function push(new_data) {
var new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
// Function to delete a node in a
// singly Linked List.
function deleteNode(key) {
// Store head node
var temp = head, prev = null;
// If head node itself holds the
// key to be deleted
if (temp != null && temp.data == key) {
// Changed head
head = temp.next;
return;
}
// Search for the key to be deleted,
// keep track of the previous node
// as we need to change temp.next
while (temp != null && temp.data != key) {
prev = temp;
temp = temp.next;
}
// If key was not present in linked list
if (temp == null)
return;
// Unlink the node from linked list
prev.next = temp.next;
}
// Function to delete all the nodes
// from linked list containing
// even numbers.
function deleteEvenNodes() {
var ptr = head;
// loop to iterate the linked list
while (ptr != null) {
// If containing element is even
if (ptr.data % 2 == 0) {
// Delete the node
deleteNode(ptr.data);
}
ptr = ptr.next;
}
}
// This function prints contents of linked
// list starting from the given node
function printList() {
var ptr = head;
while (ptr != null) {
document.write(ptr.data + "-> ");
ptr = ptr.next;
}
}
// Driver code
push(19);
push(18);
push(3);
push(4);
push(1);
document.write("<br/>Initial List: ");
printList();
deleteEvenNodes();
document.write("<br/>Final List: ");
printList();
// This code contributed by aashish1995
</script>
Producción
Initial List: 1 -> 4 -> 3 -> 18 -> 19 -> Final List: 1 -> 3 -> 19 ->
Complejidad del tiempo: O(N^2)
Como la complejidad de la función deleteNode es O(N) y necesitamos llamarla para cada número par.
Espacio Auxiliar: O(1)
Como espacio adicional constante se utiliza.
Enfoque 2:
La idea es recorrer la lista enlazada uno por uno y obtener el puntero de los Nodes que tienen valores pares. También siga eliminando los Nodes que tienen valores pares utilizando el método utilizado en esta publicación.
Queremos que la complejidad del tiempo sea O(1) para eliminar un Node determinado a fin de obtener una solución O(N) para el enfoque general.
El algoritmo para la función deleteNode:
- En la función deleteNode obtenemos directamente el puntero del Node a eliminar.
- Copie el valor del siguiente Node a este Node.
- eliminar el siguiente Node.
Lo único que debe tener en cuenta es que el Node que se eliminará no debe ser el último Node si usamos el método anterior para eliminar el Node, pero da el resultado en tiempo O (1), por lo que usaremos esto en nuestro solución.
El algoritmo para la función deleteEvenNodes:
- Obtenemos el encabezado de la lista enlazada como un parámetro de función.
- Use variables de puntero ficticias ptr y prev que se usan para almacenar el Node actual y anterior respectivamente.
- Recorra la lista enlazada antes del último elemento usando un bucle while y haga lo siguiente:
- elimine los Nodes con valores impares y siga actualizando los punteros anterior y ptr
- El caso del último Node se maneja explícitamente al final.
Implementación completa del enfoque anterior:
C++
// C++ implementation to delete all
// even valed nodes from the singly linked list
#include <bits/stdc++.h>
using namespace std;
// Node of the singly linked list
struct Node {
int data;
struct Node* next;
};
// Function to insert a node at
// the beginning of the singly
// Linked List
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
// Function to delete a node in a
// singly Linked List.
// node --> Pointer to given node
void deleteNode(struct Node* node)
{
// copy the next node's value in current node
node->data = node->next->data;
// store the pointer to node's next in a temp variable
struct Node* temp = node->next;
// connect the node with node's next's next
node->next = node->next->next;
// delete the temp
delete (temp);
}
// Function to delete all the
// even valued nodes from the
// singly linked list
void deleteEvenNodes(Node** head_ref)
{
Node* ptr = *head_ref;
Node* prev;
// mark the current head with ptr pointer
while (ptr != NULL && ptr->next != NULL) {
// traverse the linked list before the last element
if (ptr->data % 2 == 0)
deleteNode(ptr);
// delete the node if the value of the node is even
else {
prev = ptr;
ptr = ptr->next;
}
// move the pointer to the next element and store
// the prev node
}
if (ptr == *head_ref && ptr->data % 2 == 0)
*head_ref = NULL;
else if (ptr->data % 2 == 0) {
prev->next = NULL;
delete ptr;
}
}
// This function prints contents
// of linked list starting from
// the given node
void printList(struct Node* node)
{
while (node != NULL) {
printf(" %d -> ", node->data);
node = node->next;
}
}
// Driver code
int main()
{
// Start with the empty list
Node* head = NULL;
push(&head, 2);
push(&head, 6);
push(&head, 15);
push(&head, 16);
push(&head, 18);
printf("Initial List: ");
printList(head);
deleteEvenNodes(&head);
printf("\nFinal List: ");
printList(head);
}
// This code was contributed by Abhijeet Kumar
Java
// Java implementation to delete all
// even valued nodes from the singly linked list
class LinkedList{
// head of list
Node head;
// Linked list Node
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
// Function to insert a node at
// the beginning of the singly
// Linked List
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
// Function to delete a node in a
// singly Linked List.
void deleteNode(Node node)
{
// copy the next node's value in current node
node.data = node.next.data;
// connect the node with node's next's next
node.next = node.next.next;
}
// Function to delete all the nodes
// from linked list containing
// even numbers.
void deleteEvenNodes()
{
Node ptr = head;
Node prev = null;
//mark the current head with ptr pointer
while (ptr!=null && ptr.next != null)
{
// traverse the linked list before the last element
if (ptr.data % 2 == 0)
deleteNode(ptr);
// delete the node if the value of the node is even
else{
prev = ptr;
ptr = ptr.next;
}
// move the pointer to the next element and store the previous pointer
}
if(ptr==head && ptr.data % 2 == 0)
head = null;
else if(ptr.data % 2 == 0)
prev.next = null;
}
// This function prints contents of linked
// list starting from the given node
public void printList()
{
Node ptr = head;
while (ptr != null)
{
System.out.print(ptr.data + "-> ");
ptr = ptr.next;
}
}
// Driver code
public static void main(String[] args)
{
LinkedList head = new LinkedList();
head.push(2);
head.push(6);
head.push(15);
head.push(16);
head.push(18);
System.out.print("\nInitial List: ");
head.printList();
head.deleteEvenNodes();
System.out.print("\nFinal List: ");
head.printList();
}
}
// This code is contributed by Abhijeet Kumar(abhijeet19403)
Python3
# Python3 implementation to delete all
# even valued nodes from the singly linked list
# Node class
class Node:
# Function to initialize the node object
def __init__(self, data):
# Assign data
self.data = data
# Initialize
# next as null
self.next = None
# Linked List Class
class LinkedList:
# Function to initialize the
# LinkedList class.
def __init__(self):
# Initialize head as None
self.head = None
# This function insert a new node at
# the beginning of the linked list
def push(self, new_data):
# Create a new Node
new_node = Node(new_data)
# Make next of new Node as head
new_node.next = self.head
# Move the head to point to new Node
self.head = new_node
# Method to print the linked list
def printList(self):
# Object to iterate
# the list
ptr = self.head
# Loop to iterate list
while(ptr != None):
print(ptr.data, '-> ', end = '')
# Moving the iterating object
# to next node
ptr = ptr.next
print()
# Method to delete a node in
# a singly linked list.
def deleteNode(self,node):
# copy the next node's value in current node
node.data = node.next.data
# connect the node with node's next's next
node.next = node.next.next
# Method to delete all the
# even valued nodes from singly
# linked list.
def deleteEvenNodes(self):
#mark the current head with ptr pointer
ptr = self.head
prev = self.head
# traverse the linked list before the last element
while (ptr!=None and ptr.next != None):
# delete the node if the value of the node is even
if (ptr.data % 2 == 0):
self.deleteNode(ptr)
# move the pointer to the next element and store the previous pointer
else:
prev = ptr
ptr = ptr.next
if(ptr==self.head and ptr.data % 2 == 0):
head = None
elif(ptr.data % 2 == 0):
prev.next = None
# Driver code
if __name__=='__main__':
head = LinkedList()
# Pushing elements at start
# of linked list.
head.push(18)
head.push(16)
head.push(15)
head.push(6)
head.push(2)
# Print initial linked list
print("Initial list: ", end = '')
head.printList()
# Calling the function to delete
# nodes containing even numbers.
head.deleteEvenNodes()
# Print the final list
print("Final list: ", end = '')
head.printList()
# This code is contributed by Abhijeet Kumar(abhijeet19403)
C#
// C# implementation to delete all
// even valued nodes from the singly linked list
using System;
class List{
// head of list
Node head;
// Linked list Node
public class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
// Function to insert a node at
// the beginning of the singly
// Linked List
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
// Function to delete a node in a
// singly Linked List.
void deleteNode(Node node)
{
// copy the next node's value in current node
node.data = node.next.data;
// connect the node with node's next's next
node.next = node.next.next;
}
// Function to delete
// all the nodes from
// linked list containing
// even numbers.
void deleteEvenNodes()
{
Node ptr = head;
Node prev = null;
//mark the current head with ptr pointer
while (ptr!=null && ptr.next != null)
{
// traverse the linked list before the last element
if (ptr.data % 2 == 0)
deleteNode(ptr);
// delete the node if the value of the node is even
else{
prev = ptr;
ptr = ptr.next;
}
// move the pointer to the next element and store the previous pointer
}
if(ptr==head && ptr.data % 2 == 0)
head = null;
else if(ptr.data % 2 == 0)
prev.next = null;
}
// This function prints contents of linked
// list starting from the given node
public void printList()
{
Node ptr = head;
while (ptr != null)
{
Console.Write(ptr.data + "-> ");
ptr = ptr.next;
}
}
// Driver code
public static void Main(String []args)
{
List head = new List();
head.push(2);
head.push(6);
head.push(15);
head.push(16);
head.push(18);
Console.Write("\nInitial List: ");
head.printList();
head.deleteEvenNodes();
Console.Write("\nFinal List: ");
head.printList();
}
}
// This code contributed by Abhijeet Kumar(abhijeet19403)
Javascript
<script>
// javascript implementation to delete all
// even nodes from the singly linked list
// head of list
var head;
// Linked list Node
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
// Function to insert a node at
// the beginning of the singly
// Linked List
function push(new_data) {
var new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
// Function to delete a node in a
// singly Linked List.
void deleteNode(Node node)
{
// copy the next node's value in current node
node.data = node.next.data;
// connect the node with node's next's next
node.next = node.next.next;
}
// Function to delete all the nodes
// from linked list containing
// even numbers.
function deleteEvenNodes() {
var ptr = head,prev = null;
//mark the current head with ptr pointer
while (ptr!=null && ptr.next != null)
{
// traverse the linked list before the last element
if (ptr.data % 2 == 0)
deleteNode(ptr);
// delete the node if the value of the node is even
else{
prev = ptr;
ptr = ptr.next;
}
// move the pointer to the next element and store the previous pointer
}
if(ptr==head && ptr.data % 2 == 0)
head = null;
else if(ptr.data % 2 == 0)
prev.next = null;
}
// This function prints contents of linked
// list starting from the given node
function printList() {
var ptr = head;
while (ptr != null) {
document.write(ptr.data + "-> ");
ptr = ptr.next;
}
}
// Driver code
push(2);
push(6);
push(15);
push(16);
push(18);
document.write("<br/>Initial List: ");
printList();
deleteEvenNodes();
document.write("<br/>Final List: ");
printList();
// This code contributed by Abhijeet Kumar(abhijeet19403)
</script>
Producción
Initial List: 18 -> 16 -> 15 -> 6 -> 2 -> Final List: 15 ->
Complejidad de tiempo: O(N)
Como estamos visitando cada Node y eliminando el Node de valor impar, que es la operación O (1).
Espacio Auxiliar: O(1)
Como espacio adicional constante se utiliza.
Este enfoque fue aportado por Abhijeet Kumar. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por ShivaTeja2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA