Posted on by Kalkicode

# Delete all prime nodes from a Singly Linked List

The problem at hand is to delete all prime nodes from a singly linked list. A singly linked list is a linear data structure where each element, known as a node, holds a value and a reference to the next node in the sequence. In this case, we are dealing with a singly linked list of integers. The task is to identify and remove all nodes that contain prime numbers from the linked list.

## Problem Statement

Given a singly linked list of integers, we need to delete all nodes that contain prime numbers.

## Example

``7 -> 1 -> 8 -> 2 -> 4 -> 23 -> 37 -> NULL``

After deleting prime nodes, the list becomes:

``1 -> 8 -> 4 -> NULL``

## Idea to Solve the Problem

To solve this problem, we can iterate through the linked list while checking each node's value for primality. If a prime node is found, we will remove it from the list. We can maintain three pointers: `temp`, `hold`, and `prev`. The `temp` pointer will traverse through the list, `hold` will keep track of the prime node to be removed, and `prev` will be used to adjust the references after removing nodes.

## Algorithm

1. Initialize `temp` as the head of the linked list and `hold` and `prev` as null.
2. Iterate through the linked list using the `temp` pointer.
• If the value of `temp` node is prime:
• Set `hold` as `temp` to mark the prime node for removal.
• Else:
• Set `prev` as `temp` (since we need to keep track of the previous non-prime node).
• Move `temp` to the next node.
3. If `hold` is not null:
• If `hold` is the head node:
• Update the head to skip the prime node (i.e., set `head` as `temp`).
• Else:
• Update the `next` reference of the previous non-prime node to skip the prime node (i.e., set `prev.next` as `temp`).
4. Repeat steps 2-3 until the end of the linked list is reached.
5. The linked list will now contain only the non-prime nodes.

## Pseudocode

``````function deletePrimeNodes():
hold = null
prev = null

while temp is not null:
if isPrime(temp.data):
hold = temp
else:
prev = temp

temp = temp.next

if hold is not null:
else:
prev.next = temp
hold = null``````

## Time Complexity

The time complexity of the algorithm is determined by the traversal of the linked list. In the worst case, each node is visited once, resulting in a time complexity of O(n), where n is the number of nodes in the linked list.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post