Dada una lista circular enlazada individualmente que contiene N Nodes. La tarea es eliminar todos los Nodes de la lista que son primos.
Ejemplos:
Entrada: 9->11->32->6->13->20
Salida: 9 32 6 20Entrada: 6->11->16->21->17->10
Salida: 6 16 21 10
Enfoque: La idea es recorrer los Nodes de la lista circular de enlaces sencillos uno por uno y obtener el puntero de los Nodes que son primos. Elimine esos Nodes siguiendo el enfoque utilizado en la publicación: Eliminar un Node de la lista enlazada circular .
A continuación se muestra la implementación de la idea anterior:
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to delete all prime
// 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
ptr1->next = ptr1; // For the first node
*head_ref = ptr1;
}
// Delete the node if it is prime
void deleteNode(Node* head_ref, Node* del)
{
struct Node *temp = head_ref, *temp2 = head_ref;
// 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 check if a number is prime
bool isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// Function to delete all prime nodes
// from the singly circular linked list
Node* deletePrimeNodes(Node* head)
{
if (head == NULL)
return NULL;
struct Node* ptr = head;
struct Node* temp;
// setting up the head node to the first non prime node
while (isPrime(ptr->data)) {
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 prime
// 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 (isPrime(ptr->data))
deleteNode(head, ptr);
ptr = temp;
} while (ptr != head);
return head;
}
// Function to print nodes in a
// given singly 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->32->6->13->20
push(&head, 20);
push(&head, 13);
push(&head, 6);
push(&head, 32);
push(&head, 11);
push(&head, 9);
cout << "Given List : ";
printList(head);
cout << "\nList After deleting prime nodes : ";
head = deletePrimeNodes(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;
}
else
ptr1.next = ptr1; // For the first node
head_ref = ptr1;
return head_ref;
}
// Delete the node if it is prime
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 check if a number is prime
static boolean isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// Function to delete all prime nodes
// from the singly circular linked list
static Node deletePrimeNodes(Node head)
{
Node ptr = head;
Node next;
// traverse list till the endl
// if node is prime then delete it
do
{
// if node is prime
if (isPrime(ptr.data))
deleteNode(head, ptr);
// point to next node
next = ptr.next;
ptr = next;
}
while (ptr != head);
return head;
}
// Function to print nodes in a
// given singly 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.32.6.13.20
head=push(head, 20);
head=push(head, 13);
head=push(head, 6);
head=push(head, 32);
head=push(head, 11);
head=push(head, 9);
System.out.println("Given List : ");
printList(head);
System.out.println( "\nList After deleting prime nodes : ");
head=deletePrimeNodes(head);
printList(head);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to delete all prime
# 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 prime
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
# Finally, free the memory
# occupied by delete
# free(delete)
return head_ref
# Function to check if a number is prime
def isPrime(n):
# Corner cases
if (n <= 1):
return False
if (n <= 3):
return True
# This is checked so that we can skip
# middle five numbers in below loop
if (n % 2 == 0 or n % 3 == 0):
return False
for i in range(5, n + 1, 6):
if (i * i < n + 2 and
(n % i == 0 or
n % (i + 2) == 0)):
return False
return True
# Function to delete all prime nodes
# from the singly circular linked list
def deletePrimeNodes( head):
ptr = head
#next
# traverse list till the endl
# if node is prime then delete it
# if (isPrime(ptr.data)!=True):
# deleteNode(head, ptr)
# point to next node
next = ptr.next
ptr = next
while (ptr != head):
# if node is prime
if (isPrime(ptr.data) == True):
deleteNode(head, ptr)
# point to next node
next = ptr.next
ptr = next
return head
# Function to print nodes in a
# given singly linked list
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
# 9.11.32.6.13.20
head = push(head, 20)
head = push(head, 13)
head = push(head, 6)
head = push(head, 32)
head = push(head, 11)
head = push(head, 9)
print("Given List : ", end = "")
printList(head)
print( "\nList After deleting",
"prime nodes : ", end = "")
head = deletePrimeNodes(head)
printList(head)
# This code is contributed by Srathore
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;
}
else
ptr1.next = ptr1; // For the first node
head_ref = ptr1;
return head_ref;
}
// Delete the node if it is prime
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 check if a number is prime
static bool isPrime(int n)
{
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (int i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// Function to delete all prime nodes
// from the singly circular linked list
static Node deletePrimeNodes(Node head)
{
Node ptr = head;
Node next;
// traverse list till the endl
// if node is prime then delete it
do
{
// if node is prime
if (isPrime(ptr.data))
deleteNode(head, ptr);
// point to next node
next = ptr.next;
ptr = next;
}
while (ptr != head);
return head;
}
// Function to print nodes in a
// given singly 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()
{
// Initialize lists as empty
Node head = null;
// Created linked list will be
// 9.11.32.6.13.20
head=push(head, 20);
head=push(head, 13);
head=push(head, 6);
head=push(head, 32);
head=push(head, 11);
head=push(head, 9);
Console.WriteLine("Given List : ");
printList(head);
Console.WriteLine( "\nList After deleting prime nodes : ");
head=deletePrimeNodes(head);
printList(head);
}
}
/* This code contributed by PrinciRaj1992 */
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;
} else
ptr1.next = ptr1; // For the first node
head_ref = ptr1;
return head_ref;
}
// Delete the node if it is prime
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 check if a number is prime
function isPrime(n) {
// Corner cases
if (n <= 1)
return false;
if (n <= 3)
return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n % 2 == 0 || n % 3 == 0)
return false;
for (i = 5; i * i <= n; i = i + 6)
if (n % i == 0 || n % (i + 2) == 0)
return false;
return true;
}
// Function to delete all prime nodes
// from the singly circular linked list
function deletePrimeNodes(head) {
var ptr = head;
var next;
// traverse list till the endl
// if node is prime then delete it
do {
// if node is prime
if (isPrime(ptr.data))
deleteNode(head, ptr);
// point to next node
next = ptr.next;
ptr = next;
} while (ptr != head);
return head;
}
// Function to print nodes in a
// given singly 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.32.6.13.20
head = push(head, 20);
head = push(head, 13);
head = push(head, 6);
head = push(head, 32);
head = push(head, 11);
head = push(head, 9);
document.write("Given List : <br/>");
printList(head);
document.write(
"<br/>List After deleting prime nodes : <br/>"
);
head = deletePrimeNodes(head);
printList(head);
// This code contributed by aashish1995
</script>
Producción
Given List : 9 11 32 6 13 20 List After deleting prime nodes : 9 32 6 20
Complejidad de tiempo: O(N * sqrt(N))
Espacio auxiliar: O(1)