Dada una lista circular enlazada individualmente que contiene N Nodes, la tarea es eliminar todos los Nodes de la lista que contiene elementos cuya suma de dígitos es par.
Ejemplos:
Entrada: CLL = 9 -> 11 -> 34 -> 6 -> 13 -> 21
Salida: 9 -> 34 -> 21
Explicación:
La lista circular enlazada individualmente contiene:
9 -> 9
11 -> 1 + 1 = 2
34 -> 3 + 4 = 7
6 -> 6
13 -> 1 + 3 = 4
21 -> 2 + 1 = 3
Aquí, la suma de dígitos para los Nodes que contienen 11, 6 y 13 son pares.
Por lo tanto, estos Nodes se han eliminado.Entrada: 5 -> 11 -> 16 -> 21 -> 17 -> 10
Salida: 5 -> 16 -> 21 -> 10
Explicación:
La lista enlazada contiene valores de suma de dos dígitos 11 y 17.
Por lo tanto, estos Nodes han sido eliminado
Enfoque: La idea es recorrer los Nodes de la lista circular de enlaces simples uno por uno y para cada Node, encontrar la suma de dígitos para el valor presente en el Node iterando a través de cada dígito. Si la suma de los dígitos es par, elimine los Nodes . De lo contrario, continúa.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to remove all
// the Even Digit Sum Nodes 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)
{
// Create a new node and make head as next
// of it.
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) {
// Find the node before head
// and update next of it.
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
// Point for the first node
ptr1->next = ptr1;
*head_ref = ptr1;
}
// Function to delete the node from a
// Circular Linked list
void deleteNode(Node* head_ref, Node* del)
{
struct Node* temp = head_ref;
// Traverse list till not found
// delete node
while (temp->next != del) {
temp = temp->next;
}
// Copy the address of the node
temp->next = del->next;
// Finally, free the memory
// occupied by del
free(del);
return;
}
// Function to find the digit sum
// for a number
int digitSum(int num)
{
int sum = 0;
while (num) {
sum += (num % 10);
num /= 10;
}
return sum;
}
// Function to delete all the Even Digit Sum Nodes
// from the singly circular linked list
Node* deleteEvenDigitSumNodes(Node* head)
{
struct Node* ptr = head;
struct Node* temp;
//setting up the head node to the first non even digit sum node
while(digitSum(ptr->data)%2==0){
ptr=ptr->next;
if(ptr==head){
return NULL;
}
}
temp = ptr;
Node* temp2=ptr;
ptr=ptr->next;
//setting up the last node next to the first non even digit sum node
while(ptr!=head){
temp2=ptr;
ptr=ptr->next;
}
temp2->next=temp;
head=temp;
ptr=head;
// traverse list till the endl
// if node is prime then delete it
do {
temp = ptr->next;
// if node is prime
if (digitSum(ptr->data)%2==0)
deleteNode(head, ptr);
ptr = temp;
} while (ptr != head);
return head;
}
// Function to print nodes in a
// given Circular linked list
void printList(struct Node* head)
{
if(!head) printf("NULL");
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
// 9->11->34->6->13->21
push(&head, 21);
push(&head, 13);
push(&head, 6);
push(&head, 34);
push(&head, 11);
push(&head, 9);
head = deleteEvenDigitSumNodes(head);
printList(head);
return 0;
}
Java
// Java program to remove all
// the Even Digit Sum Nodes from a
// circular singly linked list
import java.util.*;
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)
{
// Create a new node and make head
// as next of it.
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)
{
// Find the node before head
// and update next of it.
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
}
else
// Point for the first node
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
// Function to delete the node from a
// Circular Linked list
static void 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 the address of the node
temp.next = del.next;
// Finally, free the memory
// occupied by del
del = null;
return;
}
// Function to find the digit sum
// for a number
static int digitSum(int num)
{
int sum = 0;
while (num > 0)
{
sum += (num % 10);
num /= 10;
}
return sum;
}
// Function to delete all the Even Digit
// Sum Nodes from the singly circular
// linked list
static void deleteEvenDigitSumNodes(Node head)
{
Node ptr = head;
Node next;
// Traverse the list till the end
do
{
// If the node's data is Fibonacci,
// delete node 'ptr'
if (!(digitSum(ptr.data) % 2 == 1))
deleteNode(head, ptr);
// Point to the next node
next = ptr.next;
ptr = next;
} while (ptr != head);
}
// Function to print nodes in a
// given Circular linked list
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
// 9.11.34.6.13.21
head = push(head, 21);
head = push(head, 13);
head = push(head, 6);
head = push(head, 34);
head = push(head, 11);
head = push(head, 9);
deleteEvenDigitSumNodes(head);
printList(head);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program to remove all # the Even Digit Sum Nodes from a # circular singly linked list # 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): # Create a new node and make head as next # of it. 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): # Find the node before head # and update next of it. while (temp.next != head_ref): temp = temp.next temp.next = ptr1 else: # Point for the first node ptr1.next = ptr1 head_ref = ptr1 return head_ref # Function to delete the node from a # Circular Linked list def deleteNode(head_ref, delt): temp = head_ref # If node to be deleted is head node if (head_ref == delt): head_ref = delt.next # Traverse list till not found # delete node while (temp.next != delt): temp = temp.next # Copy the address of the node temp.next = delt.next # Finally, free the memory # occupied by delt del (delt) return # Function to find the digit sum # for a number def digitSum(num): sum = 0 while (num != 0): sum += (num % 10) num //= 10 return sum # Function to delete all the Even Digit # Sum Nodes from the singly circular linked list def deleteEvenDigitSumNodes(head): ptr = head next = None # Traverse the list till the end while True: # If the node's data is Fibonacci, # delete node 'ptr' if (not (digitSum(ptr.data) & 1)): deleteNode(head, ptr) # Point to the next node next = ptr.next ptr = next if (ptr == head): break # Function to print nodes in a # given Circular linked list def printList(head): temp = head if (head != None): while True: print(temp.data, end = ' ') temp = temp.next if (temp == head): break # Driver code if __name__=='__main__': # Initialize lists as empty head = None # Created linked list will be # 9.11.34.6.13.21 head = push(head, 21) head = push(head, 13) head = push(head, 6) head = push(head, 34) head = push(head, 11) head = push(head, 9) deleteEvenDigitSumNodes(head) printList(head) # This code is contributed by rutvik_56
C#
// C# program to remove all
// the Even Digit Sum Nodes from a
// circular singly linked list
using System;
class GFG{
// Structure for a node
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)
{
// Create a new node and make head
// as next of it.
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)
{
// Find the node before head
// and update next of it.
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
}
else
// Point for the first node
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
// Function to delete the node from a
// Circular Linked list
static void 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 the address of the node
temp.next = del.next;
// Finally, free the memory
// occupied by del
del = null;
return;
}
// Function to find the digit sum
// for a number
static int digitSum(int num)
{
int sum = 0;
while (num > 0)
{
sum += (num % 10);
num /= 10;
}
return sum;
}
// Function to delete all the Even Digit
// Sum Nodes from the singly circular
// linked list
static void deleteEvenDigitSumNodes(Node head)
{
Node ptr = head;
Node next;
// Traverse the list till the end
do
{
// If the node's data is Fibonacci,
// delete node 'ptr'
if (!(digitSum(ptr.data) % 2 == 1))
deleteNode(head, ptr);
// Point to the next node
next = ptr.next;
ptr = next;
} while (ptr != head);
}
// Function to print nodes in a
// given Circular linked list
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
// 9.11.34.6.13.21
head = push(head, 21);
head = push(head, 13);
head = push(head, 6);
head = push(head, 34);
head = push(head, 11);
head = push(head, 9);
deleteEvenDigitSumNodes(head);
printList(head);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program to remove all
// the Even Digit Sum Nodes 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) {
// Create a new node and make head
// as next of it.
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) {
// Find the node before head
// and update next of it.
while (temp.next != head_ref)
temp = temp.next;
temp.next = ptr1;
} else
// Point for the first node
ptr1.next = ptr1;
head_ref = ptr1;
return head_ref;
}
// Function to delete the node from a
// Circular Linked list
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 the address of the node
temp.next = del.next;
// Finally, free the memory
// occupied by del
del = null;
return;
}
// Function to find the digit sum
// for a number
function digitSum(num) {
var sum = 0;
while (num > 0) {
sum += (num % 10);
num = parseInt(num/10);
}
return sum;
}
// Function to delete all the Even Digit
// Sum Nodes from the singly circular
// linked list
function deleteEvenDigitSumNodes(head) {
var ptr = head;
var next;
// Traverse the list till the end
do {
// If the node's data is Fibonacci,
// delete node 'ptr'
if (!(digitSum(ptr.data) % 2 == 1))
deleteNode(head, ptr);
// Point to the next node
next = ptr.next;
ptr = next;
} while (ptr != head);
}
// Function to print nodes in a
// given Circular linked list
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
// 9.11.34.6.13.21
head = push(head, 21);
head = push(head, 13);
head = push(head, 6);
head = push(head, 34);
head = push(head, 11);
head = push(head, 9);
deleteEvenDigitSumNodes(head);
printList(head);
// This code contributed by aashish1995
</script>
Producción
9 34 21
Complejidad temporal: O(KN), donde N es el tamaño de la lista enlazada y K es el número máximo de dígitos en cualquier Node.
Espacio Auxiliar: (1)
Publicación traducida automáticamente
Artículo escrito por muskan_garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA