Replace every node with closest Prime number in a Singly Linked List
Given a linked list, the task is to replace every node with its closest prime number and return the modified list.
Examples:
Input: List: 1 -> 2 -> 8 -> 7 -> 14 -> NULL
Output: 2 -> 2 -> 7 -> 7 -> 13 -> NULL
Explanation: For the first node 1, the closest prime number is 2. For the second node 2, the closest prime number is 2 itself. For the third node 8, the closest prime number is 7. For the fourth node 7, the closest prime number is 7 itself. For the fifth node 14, the closest prime number is 13.Input: List: 2 -> 2 -> 2 -> NULL
Output: 2 -> 2 -> 2 -> NULL
Explanation: Since every node in the linked list is the number 2, which is itself a prime number, each node is already the closest prime number to itself. Therefore, there is no need to modify any node in the linked list, and the output remains the same as the input.
Approach: To solve the problem follow the below idea:
The approach is to replaces each node’s value in a singly linked list with the closest prime number. It does this by iterating through the list and for each node, it checks if its value is a prime number. If it’s prime, no change is made. If it’s not prime, the code searches for the closest prime number by incrementally checking smaller and larger values. This approach ensures that the modified linked list contains prime numbers or numbers closest to prime numbers.
Steps of this approach:
- Define a function isPrime(n) to check if a given number n is prime. It returns true if the number is prime and false otherwise.
- Create a function closestPrime(n) that takes a number n as input and finds the closest prime number to it. If n is already prime, it returns n. Otherwise, it iteratively checks smaller and larger values to find the closest prime, moving toward the desired prime number.
- Create a function replaceWithClosestPrime(head) that takes the head of a linked list as input. Initialize a current pointer curr to the head of the list.
- Traverse the linked list using a while loop until curr reaches the end (i.e., it becomes NULL).
- For each node, call the closestPrime function to find the closest prime number to the node’s data value and update the node’s data with this closest prime.
- Move the curr pointer to the next node in the list.
- Return the modified head of the linked list.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Definition for singly-linked list. struct Node { // Data stored in the node int data; // Pointer to the next node Node* next; Node( int data) { this ->data = data; next = NULL; } }; // Function to check if a number is prime or not bool isPrime( int n) { if (n <= 1) { // Numbers less than or equal to // 1 are not prime return false ; } for ( int i = 2; i <= sqrt (n); i++) { // If there's a divisor other than // 1 and n, it's not prime if (n % i == 0) { return false ; } } // If no divisors found, the number is // prime return true ; } // Function to find the closest prime number // for a given number int closestPrime( int n) { // If the number is already prime, // return it if (isPrime(n)) { return n; } // Initialize smaller to one less than n int smaller = n - 1; // Initialize larger to one more than n int larger = n + 1; while ( true ) { // Return the smaller prime if found if (isPrime(smaller)) { return smaller; } // Return the larger prime if found if (isPrime(larger)) { return larger; } smaller--; larger++; } } // Function to replace every node with the // closest prime number in a linked list Node* replaceWithClosestPrime(Node* head) { Node* curr = head; while (curr != NULL) { // Replace the node's data with the // closest prime curr->data = closestPrime(curr->data); // Move to the next node in the // list curr = curr->next; } return head; } // Function to print the linked list void printList(Node* head) { Node* curr = head; while (curr != NULL) { // Print the node's data cout << curr->data; if (curr->next != NULL) { cout << " -> " ; } else { cout << " -> NULL" ; } // Move to the next node curr = curr->next; } cout << endl; } // Drivers code int main() { // Example 1 Node* head1 = new Node(1); head1->next = new Node(2); head1->next->next = new Node(8); head1->next->next->next = new Node(7); head1->next->next->next->next = new Node(14); cout << "Original List : " ; printList(head1); head1 = replaceWithClosestPrime(head1); cout << "Modified List : " ; printList(head1); return 0; } |
Java
import java.util.*; // Definition for singly-linked list. class Node { // Data stored in the node int data; // Pointer to the next node Node next; Node( int data) { this .data = data; this .next = null ; } } public class Main { // Function to check if a number is prime or not static boolean isPrime( int n) { if (n <= 1 ) { // Numbers less than or equal to 1 are not prime return false ; } for ( int i = 2 ; i <= Math.sqrt(n); i++) { // If there's a divisor other than 1 and n, it's not prime if (n % i == 0 ) { return false ; } } // If no divisors found, the number is prime return true ; } // Function to find the closest prime number for a given number static int closestPrime( int n) { // If the number is already prime, return it if (isPrime(n)) { return n; } // Initialize smaller to one less than n int smaller = n - 1 ; // Initialize larger to one more than n int larger = n + 1 ; while ( true ) { // Return the smaller prime if found if (isPrime(smaller)) { return smaller; } // Return the larger prime if found if (isPrime(larger)) { return larger; } smaller--; larger++; } } // Function to replace every node with the closest prime number in a linked list static Node replaceWithClosestPrime(Node head) { Node curr = head; while (curr != null ) { // Replace the node's data with the closest prime curr.data = closestPrime(curr.data); // Move to the next node in the list curr = curr.next; } return head; } // Function to print the linked list static void printList(Node head) { Node curr = head; while (curr != null ) { // Print the node's data System.out.print(curr.data); if (curr.next != null ) { System.out.print( " -> " ); } else { System.out.print( " -> NULL" ); } // Move to the next node curr = curr.next; } System.out.println(); } // Driver code public static void main(String[] args) { // Example 1 Node head1 = new Node( 1 ); head1.next = new Node( 2 ); head1.next.next = new Node( 8 ); head1.next.next.next = new Node( 7 ); head1.next.next.next.next = new Node( 14 ); System.out.print( "Original List : " ); printList(head1); head1 = replaceWithClosestPrime(head1); System.out.print( "Modified List : " ); printList(head1); } } |
Python3
# Python code to implement above code import math # Definition for singly-linked list. class Node: def __init__( self , data): self .data = data self . next = None # Function to check if a number is # prime or not def is_prime(n): if n < = 1 : # Numbers less than or equal to 1 # are not prime return False for i in range ( 2 , int (math.sqrt(n)) + 1 ): # If there's a divisor other than 1 # and n, it's not prime if n % i = = 0 : return False # If no divisors found, the number is prime return True # Function to find the closest prime number # for a given number def closest_prime(n): # If the number is already prime, # return it if is_prime(n): return n # Initialize smaller to one less than n smaller = n - 1 # Initialize larger to one more than n larger = n + 1 while True : # Return the smaller prime if found if is_prime(smaller): return smaller # Return the larger prime if found if is_prime(larger): return larger smaller - = 1 larger + = 1 # Function to replace every node with the closest # prime number in a linked list def replace_with_closest_prime(head): curr = head while curr is not None : # Replace the node's data with the # closest prime curr.data = closest_prime(curr.data) # Move to the next node in the list curr = curr. next return head # Function to print the linked list def print_list(head): curr = head while curr is not None : # Print the node's data print (curr.data, end = "") if curr. next is not None : print ( " -> " , end = "") else : print ( " -> NULL" , end = "") # Move to the next node curr = curr. next print () # Drivers code # Example 1 head1 = Node( 1 ) head1. next = Node( 2 ) head1. next . next = Node( 8 ) head1. next . next . next = Node( 7 ) head1. next . next . next . next = Node( 14 ) print ( "Original List : " , end = "") print_list(head1) head1 = replace_with_closest_prime(head1) print ( "Modified List : " , end = "") print_list(head1) |
C#
using System; // Definition for singly-linked list public class Node { // Data stored in the node public int data; // Pointer to the next node public Node next; public Node( int data) { this .data = data; next = null ; } } public class LinkedList { // Function to check if a number is prime or not public static bool IsPrime( int n) { if (n <= 1) { // Numbers less than or equal to // 1 are not prime return false ; } for ( int i = 2; i <= Math.Sqrt(n); i++) { // If there's a divisor other than // 1 and n, it's not prime if (n % i == 0) { return false ; } } // If no divisors found, the number is // prime return true ; } // Function to find the closest prime number // for a given number public static int ClosestPrime( int n) { // If the number is already prime, // return it if (IsPrime(n)) { return n; } // Initialize smaller to one less than n int smaller = n - 1; // Initialize larger to one more than n int larger = n + 1; while ( true ) { // Return the smaller prime if found if (IsPrime(smaller)) { return smaller; } // Return the larger prime if found if (IsPrime(larger)) { return larger; } smaller--; larger++; } } // Function to replace every node with the // closest prime number in a linked list public static Node ReplaceWithClosestPrime(Node head) { Node curr = head; while (curr != null ) { // Replace the node's data with the // closest prime curr.data = ClosestPrime(curr.data); // Move to the next node in the list curr = curr.next; } return head; } // Function to print the linked list public static void PrintList(Node head) { Node curr = head; while (curr != null ) { // Print the node's data Console.Write(curr.data); if (curr.next != null ) { Console.Write( " -> " ); } else { Console.Write( " -> NULL" ); } // Move to the next node curr = curr.next; } Console.WriteLine(); } // Drivers code public static void Main( string [] args) { // Example 1 Node head1 = new Node(1); head1.next = new Node(2); head1.next.next = new Node(8); head1.next.next.next = new Node(7); head1.next.next.next.next = new Node(14); Console.Write( "Original List : " ); PrintList(head1); head1 = ReplaceWithClosestPrime(head1); Console.Write( "Modified List : " ); PrintList(head1); } } |
Javascript
<script> // Javascript program for the above approach // Definition for singly-linked list. class Node { constructor(data) { this .data = data; this .next = null ; } } // Function to check if a number is prime or not function isPrime(n) { if (n <= 1) { // Numbers less than or equal to 1 are not prime return false ; } for (let i = 2; i <= Math.sqrt(n); i++) { // If there's a divisor other than 1 and n, it's not prime if (n % i === 0) { return false ; } } // If no divisors found, the number is prime return true ; } // Function to find the closest prime number for a given number function closestPrime(n) { // If the number is already prime, return it if (isPrime(n)) { return n; } // Initialize smaller to one less than n let smaller = n - 1; // Initialize larger to one more than n let larger = n + 1; while ( true ) { // Return the smaller prime if found if (isPrime(smaller)) { return smaller; } // Return the larger prime if found if (isPrime(larger)) { return larger; } smaller--; larger++; } } // Function to replace every node with the closest prime number in a linked list function replaceWithClosestPrime(head) { let curr = head; while (curr !== null ) { // Replace the node's data with the closest prime curr.data = closestPrime(curr.data); // Move to the next node in the list curr = curr.next; } return head; } // Function to print the linked list function printList(head) { let curr = head; while (curr !== null ) { // Print the node's data document.write(curr.data); if (curr.next !== null ) { document.write( " -> " ); } else { document.write( " -> NULL" ); } // Move to the next node curr = curr.next; } document.write( "<br>" ); } // Drivers code // Example 1 let head1 = new Node(1); head1.next = new Node(2); head1.next.next = new Node(8); head1.next.next.next = new Node(7); head1.next.next.next.next = new Node(14); document.write( "Original List : " ); printList(head1); head1 = replaceWithClosestPrime(head1); document.write( "Modified List : " ); printList(head1); // This code is contributed by Susobhan Akhuli </script> |
Original List : 1 -> 2 -> 8 -> 7 -> 14 -> NULL Modified List : 2 -> 2 -> 7 -> 7 -> 13 -> NULL
Time Complexity: O(n * sqrt(n)) where n is the length of the linked list. This is because we are checking for primes in the closestPrime() function.
Auxiliary Space: O(1) as we are not using any extra space.