Удалить все неосновные узлы из односвязного списка

Опубликовано: 5 Января, 2022

Учитывая односвязный список, содержащий N узлов, задача состоит в том, чтобы удалить из списка все узлы, которые не являются простыми.
Примеры:

Input : List = 15 -> 16 -> 6 -> 7 -> 17 
Output : Final List = 7 -> 17
Input : List = 15 -> 3 -> 4 -> 2 -> 9 
Output : Final List = 3 ->2 
 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход : идея состоит в том, чтобы обойти узлы односвязного списка один за другим и получить указатель на узлы, которые не являются простыми. Удалите эти узлы, следуя подходу, использованному в публикации: Удалите узел из связанного списка.
Ниже представлена реализация вышеизложенной идеи:

C ++

// C++ implementation to delete all
// non-prime nodes from the singly
// linked list
#include <bits/stdc++.h>
using namespace std;
// Node of the singly linked list
struct Node {
data; int
Node* next;
};
// function to insert a node at the beginning
// of the singly Linked List
void push(Node** head_ref, int new_data)
{
Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
// 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 non-prime nodes
// from the singly linked list
void deleteNonPrimeNodes(Node** head_ref)
{
// Remove all composite nodes at the beginning
Node* ptr = *head_ref;
while (ptr != NULL && !isPrime(ptr->data))
{
Node *temp = ptr;
ptr = ptr->next;
delete (temp);
}
*head_ref = ptr;
if (ptr == NULL)
return ;
// Remove remaining nodes
Node *curr = ptr->next;
while (curr != NULL) {
if (!isPrime(curr->data))
{
ptr->next = curr->next;
delete (curr);
curr = ptr->next;
}
else
{
ptr = curr;
curr = curr->next;
}
}
}
// function to print nodes in a
// given singly linked list
void printList(Node* head)
{
while (head != NULL) {
cout << head->data << " " ;
head = head->next;
}
}
// Driver program
int main()
{
// start with the empty list
Node* head = NULL;
// create the linked list
// 15 -> 16 -> 7 -> 6 -> 17
push(&head, 17);
push(&head, 7);
push(&head, 6);
push(&head, 16);
push(&head, 15);
cout << "Original List: " ;
printList(head);
deleteNonPrimeNodes(&head);
cout << " Modified List: " ;
printList(head);
}

Джава

// Java implementation to delete all
// non-prime nodes from the singly
// linked list
class GFG
{
// Node of the singly linked list
static class Node
{
data; int
Node next;
};
// function to insert a node at the beginning
// of the singly Linked List
static Node push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
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 non-prime nodes
// from the singly linked list
static Node deleteNonPrimeNodes(Node head_ref)
{
// Remove all composite nodes at the beginning
Node ptr = head_ref;
while (ptr != null && !isPrime(ptr.data))
{
Node temp = ptr;
ptr = ptr.next;
}
head_ref = ptr;
if (ptr == null )
return null ;
// Remove remaining nodes
Node curr = ptr.next;
while (curr != null )
{
if (!isPrime(curr.data))
{
ptr.next = curr.next;
curr = ptr.next;
}
else
{
ptr = curr;
curr = curr.next;
}
}
return head_ref;
}
// function to print nodes in a
// given singly linked list
static void printList(Node head)
{
while (head != null )
{
System.out.print(head.data + " " );
head = head.next;
}
}
// Driver code
public static void main(String args[])
{
// start with the empty list
Node head = null ;
// create the linked list
// 15 . 16 . 7 . 6 . 17
head = push(head, 17 );
head = push(head, 7 );
head = push(head, 6 );
head = push(head, 16 );
head = push(head, 15 );
System.out.print( "Original List: " );
printList(head);
head = deleteNonPrimeNodes(head);
System.out.print( " Modified List: " );
printList(head);
}
}
// This code is contributed by Arnab Kundu

Python3

# Python3 implementation to delete all
# non-prime nodes from the singly
# linked list
import math
# Node of the singly linked list
class Node:
def __init__( self , data):
self .data = data
self . next = None
# function to insert a node at the beginning
# of the singly Linked List
def push(head_ref, new_data):
new_node = Node(new_data)
new_node.data = new_data
new_node. next = head_ref
head_ref = new_node
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 non-prime nodes
# from the singly linked list
def deleteNonPrimeNodes(head_ref):
# Remove all composite nodes at the beginning
ptr = head_ref
while (ptr ! = None and
isPrime(ptr.data)! = True ):
temp = ptr
ptr = ptr. next
# delete(temp)
head_ref = ptr
if (ptr = = None ):
return None
# Remove remaining nodes
curr = ptr. next
while (curr ! = None ) :
if (isPrime(curr.data) ! = True ):
ptr. next = curr. next
#delete(curr)
curr = ptr. next
else :
ptr = curr
curr = curr. next
return head_ref
# function to print nodes in a
# given singly linked list
def printList( head):
while (head ! = None ) :
print (head.data, end = " " )
head = head. next
# Driver Code
if __name__ = = '__main__' :
# start with the empty list
head = None
# create the linked list
# 15 -> 16 -> 7 -> 6 -> 17
head = push(head, 17 )
head = push(head, 7 )
head = push(head, 6 )
head = push(head, 16 )
head = push(head, 15 )
print ( "Original List: " )
printList(head)
head = deleteNonPrimeNodes(head)
print ( " Modified List: " )
printList(head)
# This code is contributed by AbhiThakur

C #

// C# implementation to delete all
// non-prime nodes from the singly
// linked list
using System;
class GFG
{
// Node of the singly linked list
public class Node
{
public data; int
public Node next;
};
// function to insert a node at the beginning
// of the singly Linked List
static Node push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
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 non-prime nodes
// from the singly linked list
static Node deleteNonPrimeNodes(Node head_ref)
{
// Remove all composite nodes
// at the beginning
Node ptr = head_ref;
while (ptr != null && !isPrime(ptr.data))
{
Node temp = ptr;
ptr = ptr.next;
}
head_ref = ptr;
if (ptr == null )
{
return null ;
}
// Remove remaining nodes
Node curr = ptr.next;
while (curr != null )
{
if (!isPrime(curr.data))
{
ptr.next = curr.next;
curr = ptr.next;
}
else
{
ptr = curr;
curr = curr.next;
}
}
return head_ref;
}
// function to print nodes in a
// given singly linked list
static void printList(Node head)
{
while (head != null )
{
Console.Write(head.data + " " );
head = head.next;
}
}
// Driver code
public static void Main(String[] args)
{
// start with the empty list
Node head = null ;
// create the linked list
// 15 . 16 . 7 . 6 . 17
head = push(head, 17);
head = push(head, 7);
head = push(head, 6);
head = push(head, 16);
head = push(head, 15);
Console.Write( "Original List: " );
printList(head);
head = deleteNonPrimeNodes(head);
Console.Write( " Modified List: " );
printList(head);
}
}
// This code is contributed by 29AjayKumar

Javascript

<script>
// javascript implementation to delete all
// non-prime nodes from the singly
// linked list // Node of the singly linked list
class Node {
Technical Scripter Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Количество чисел между L и R, взаимно простых с P
27 Февраля, 2023
Постройте матрицу, каждая строка и столбец которой содержат N и M единиц соответственно.
27 Февраля, 2023
Максимизируйте сумму трех чисел, выполнив побитовое XOR
27 Февраля, 2023
Проверьте, совпадает ли набор первых элементов X одного массива с набором первых элементов Y другого
27 Февраля, 2023
Подсчитать подстроки нечетной длины с медианой, такой же, как K-й символ строки
27 Февраля, 2023
Найти лексикографически первый идентификатор каждого домена из заданного массива идентификаторов электронной почты
27 Февраля, 2023
Найдите общее количество фигур 'X'
26 Февраля, 2023
Максимальное значение узла, которое может быть достигнуто с использованием данных соединений
26 Февраля, 2023