Posted on by Kalkicode

# Delete all Prime Nodes from a Circular Singly Linked List

In the problem of deleting all prime nodes from a circular singly linked list, we are working with a circular linked list data structure. The objective is to remove nodes from the list that contain prime values while maintaining the circular nature of the linked list.

## Problem Statement

Given a circular singly linked list, we need to delete all nodes that contain prime values. After the deletion, the circular structure of the linked list should be preserved.

## Example

Consider a circular singly linked list with the following elements: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 37. After deleting all prime nodes, the list becomes: 1 -> 4 -> 6 -> 8.

## Idea to Solve the Problem

To delete all prime nodes from a circular singly linked list, we need to iterate through the list and identify nodes with prime values. For each prime node, we'll perform the deletion while maintaining the circular structure.

## Pseudocode

Here's the pseudocode to delete all prime nodes from a circular singly linked list:

``````function deletePrimeNodes(circularLinkedList):
return
else:
hold = NULL
prev = NULL

while temp is not NULL:
if checkPrime(temp.data):
hold = temp
else:
prev = temp

temp = temp.next

temp = NULL

if hold is not NULL:

else if prev is not NULL:
prev.next = temp

hold = NULL``````

## Algorithm Explanation

1. Check if the linked list is empty. If it is, print a message and return.
2. Initialize `temp`, `hold`, and `prev` pointers to traverse the list. `hold` will store the node to be deleted, and `prev` will store the previous node.
3. Traverse the list using the `temp` pointer. If the current node's data is prime, assign it to `hold`; otherwise, assign it to `prev`.
4. Move to the next node (`temp = temp.next`).
5. If the traversal reaches the end of the list or comes back to the head, update the `temp` pointer to `NULL`.
6. If `hold` is not `NULL`, perform the deletion based on various cases:
• If `hold` is the head, update the head and consider scenarios where the head or tail needs to be updated.
• If `hold` is the tail, update the tail.
• If `prev` is not `NULL`, bypass the prime node by updating `prev.next`.
• Connect the tail to the head to maintain the circular structure.
7. Reset the `hold` pointer.

## Time Complexity

The time complexity of deleting all prime nodes from a circular singly linked list is O(n), where n is the number of nodes in the circular linked list. This is because we need to traverse the entire list to identify and remove prime nodes. The space complexity is O(1) as we are using only a constant amount of extra space for pointers.

## 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