Requisito previo: eliminar todos los Nodes pares de una lista enlazada circular
Dada una lista enlazada simple circular que contiene N Nodes, la tarea es eliminar todos los Nodes impares de la lista.
Ejemplos:
Entrada: 572->112->21->5->1->6
Salida: 572 -> 112 -> 6
Explicación: Se han eliminado todos los Nodes impares
Entrada: 9->11->32->6- >13->20
Salida: 32 -> 6 -> 20
Enfoque:
la idea es atravesar los Nodes de la lista circular de enlaces simples uno por uno y obtener el puntero de los Nodes que tienen datos impares. 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++ program to delete all odd
// node from a Circular singly linked list
#include <bits/stdc++.h>
using namespace std;
// Structure for a node
struct Node {
int data;
struct Node* next;
};
// Function to insert a node at the beginning
// of a Circular linked list
void push(struct Node** head_ref, int data)
{
struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node));
struct Node* temp = *head_ref;
ptr1->data = data;
ptr1->next = *head_ref;
// If linked list is not NULL then
// set the next of last node
if (*head_ref != NULL) {
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
// For the first node
ptr1->next = ptr1;
*head_ref = ptr1;
}
// Delete the node if it is odd
void deleteNode(Node* head_ref, Node* del)
{
struct Node* temp = head_ref;
// If node to be deleted is head node
if (head_ref == del)
head_ref = del->next;
// Traverse list till not found
// delete node
while (temp->next != del) {
temp = temp->next;
}
// Copy address of node
temp->next = del->next;
// Finally, free the memory occupied by del
free(del);
return;
}
// Function to delete all odd nodes
// from the singly circular linked list
void deleteoddNodes(Node* head)
{
struct Node* ptr = head;
struct Node* next;
// Traverse list till the end
// if the node is odd then delete it
do {
// point to next node
next = ptr->next;
// if node is odd
if ((ptr->data % 2) == 1)
deleteNode(head, ptr);
// get the next element
ptr = next;
} while (ptr != head);
}
// Function to print nodes
void printList(struct Node* head)
{
struct Node* temp = head;
if (head != NULL) {
do {
printf("%d ", temp->data);
temp = temp->next;
} while (temp != head);
}
}
// Driver code
int main()
{
// Initialize lists as empty
struct Node* head = NULL;
// Created linked list will be 56->61->57->11->12->2
push(&head, 2);
push(&head, 12);
push(&head, 11);
push(&head, 57);
push(&head, 61);
push(&head, 56);
cout << "\nList after deletion : ";
deleteoddNodes(head);
printList(head);
return 0;
}
Java
// Java program to delete all prime
// node from a Circular singly linked list
class GFG {
// Structure for a node
static class Node {
int data;
Node next;
};
// Function to insert a node at the beginning
// of a Circular linked list
static Node push(Node head_ref, int data)
{
Node ptr1 = new Node();
Node temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
// If linked list is not null then
// set the next of last node
if (head_ref != null) {
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
return head_ref;
}
else
// For the first node
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
// Delete the node if it is odd
static Node deleteNode(Node head_ref, Node del)
{
Node temp = head_ref;
// If node to be deleted is head node
if (head_ref == del)
head_ref = del.next;
// Traverse list till not found
// delete node
while (temp.next != del) {
temp = temp.next;
}
// Copy address of node
temp.next = del.next;
return head_ref;
}
// Function to delete all odd nodes
// from the singly circular linked list
static Node deleteoddNodes(Node head)
{
Node ptr = head;
Node next;
// Traverse list till the end
// if the node is odd then delete it
do {
// If node is odd
if (ptr.data % 2 == 1)
deleteNode(head, ptr);
// point to next node
next = ptr.next;
ptr = next;
} while (ptr != head);
return head;
}
// Function to print nodes
static void printList(Node head)
{
Node temp = head;
if (head != null) {
do {
System.out.printf("%d ", temp.data);
temp = temp.next;
} while (temp != head);
}
}
// Driver code
public static void main(String args[])
{
// Initialize lists as empty
Node head = null;
// Created linked list will be 56->61->57->11->12->2
head = push(head, 2);
head = push(head, 12);
head = push(head, 11);
head = push(head, 57);
head = push(head, 61);
head = push(head, 56);
System.out.println("\nList after deletion : ");
head = deleteoddNodes(head);
printList(head);
}
}
Python
# Python3 program to delete all odd
# node from a Circular singly linked list
import math
# Structure for a node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to insert a node at the beginning
# of a Circular linked list
def push(head_ref, data):
ptr1 = Node(data)
temp = head_ref
ptr1.data = data
ptr1.next = head_ref
# If linked list is not None then
# set the next of last node
if (head_ref != None):
while (temp.next != head_ref):
temp = temp.next
temp.next = ptr1
else:
ptr1.next = ptr1 # For the first node
head_ref = ptr1
return head_ref
# Delete the node if it is odd
def deleteNode(head_ref, delete):
temp = head_ref
# If node to be deleted is head node
if (head_ref == delete):
head_ref = delete.next
# Traverse list till not found
# delete node
while (temp.next != delete):
temp = temp.next
# Copy address of node
temp.next = delete.next
# Function to delete all odd nodes
# from the singly circular linked list
def deleteoddNodes(head):
ptr = head
next = None
# Traverse list till the end
# if the node is odd then delete it
# if node is odd
next = ptr.next
ptr = next
while (ptr != head):
if (ptr.data % 2 == 1):
deleteNode(head, ptr)
# point to next node
next = ptr.next
ptr = next
return head
# Function to print nodes
def printList(head):
temp = head
if (head != None):
print(temp.data, end = " ")
temp = temp.next
while (temp != head):
print(temp.data, end = " ")
temp = temp.next
# Driver code
if __name__=='__main__':
# Initialize lists as empty
head = None
# Created linked list will be 56->61->57->11->12->2
head = push(head, 2)
head = push(head, 12)
head = push(head, 11)
head = push(head, 57)
head = push(head, 61)
head = push(head, 56)
print("List after deletion : ", end = "")
head = deleteoddNodes(head)
printList(head)
C#
// C# program to delete all prime
// node from a Circular singly linked list
using System;
class GFG {
// Structure for a node
public class Node {
public int data;
public Node next;
};
// Function to insert a node at the beginning
// of a Circular linked list
static Node push(Node head_ref, int data)
{
Node ptr1 = new Node();
Node temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
// If linked list is not null then
// set the next of last node
if (head_ref != null) {
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
return head_ref;
}
else
// For the first node
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
// Delete the node if it is odd
static Node deleteNode(Node head_ref, Node del)
{
Node temp = head_ref;
// If node to be deleted is head node
if (head_ref == del)
head_ref = del.next;
// Traverse list till not found
// delete node
while (temp.next != del) {
temp = temp.next;
}
// copy address of node
temp.next = del.next;
return head_ref;
}
// Function to delete all odd nodes
// from the singly circular linked list
static Node deleteoddNodes(Node head)
{
Node ptr = head;
Node next;
// Traverse list till the end
// if the node is odd then delete it
do {
// If node is odd
if (ptr.data % 2 == 1)
deleteNode(head, ptr);
// Point to next node
next = ptr.next;
ptr = next;
} while (ptr != head);
return head;
}
// Function to print nodes
static void printList(Node head)
{
Node temp = head;
if (head != null) {
do {
Console.Write("{0} ", temp.data);
temp = temp.next;
} while (temp != head);
}
}
// Driver code
public static void Main(String[] args)
{
// Initialize lists as empty
Node head = null;
// Created linked list will be 56->61->57->11->12->2
head = push(head, 2);
head = push(head, 12);
head = push(head, 11);
head = push(head, 57);
head = push(head, 61);
head = push(head, 56);
Console.WriteLine("\nList after deletion : ");
head = deleteoddNodes(head);
printList(head);
}
}
Javascript
<script>
// JavaScript program to delete all prime
// node from a Circular singly linked list
// Structure for a node
class Node {
constructor()
{
this.data = 0;
this.next = null;
}
};
// Function to insert a node at the beginning
// of a Circular linked list
function push(head_ref, data)
{
var ptr1 = new Node();
var temp = head_ref;
ptr1.data = data;
ptr1.next = head_ref;
// If linked list is not null then
// set the next of last node
if (head_ref != null) {
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
return head_ref;
}
else
// For the first node
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
// Delete the node if it is odd
function deleteNode(head_ref, del)
{
var temp = head_ref;
// If node to be deleted is head node
if (head_ref == del)
head_ref = del.next;
// Traverse list till not found
// delete node
while (temp.next != del) {
temp = temp.next;
}
// copy address of node
temp.next = del.next;
return head_ref;
}
// Function to delete all odd nodes
// from the singly circular linked list
function deleteoddNodes(head)
{
var ptr = head;
var next;
// Traverse list till the end
// if the node is odd then delete it
do {
// If node is odd
if (ptr.data % 2 == 1)
deleteNode(head, ptr);
// Point to next node
next = ptr.next;
ptr = next;
} while (ptr != head);
return head;
}
// Function to print nodes
function printList(head)
{
var temp = head;
if (head != null) {
do {
document.write(temp.data+ " ");
temp = temp.next;
} while (temp != head);
}
}
// Driver code
// Initialize lists as empty
var head = null;
// Created linked list will be 56->61->57->11->12->2
head = push(head, 2);
head = push(head, 12);
head = push(head, 11);
head = push(head, 57);
head = push(head, 61);
head = push(head, 56);
document.write("List after deletion : ");
head = deleteoddNodes(head);
printList(head);
</script>
Producción:
List after deletion : 56 12 2
Complejidad del tiempo: O(N^2)
Como la función deleteNode toma tiempo O (N) y tenemos que procesar cada elemento en el peor de los casos
Espacio Auxiliar: O(1)
Como se utiliza espacio adicional constante
Publicación traducida automáticamente
Artículo escrito por SHUBHAMSINGH10 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA