Eliminar todos los Nodes impares de una lista enlazada circular

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *