Replace every node with closest Prime number in a Singly Linked List

Last Updated : 28 Dec, 2023

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)

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>

Output

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.