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):
    if circularLinkedList.head is NULL:
        print "Empty linked list"
        return
    else:
        temp = circularLinkedList.head
        hold = NULL
        prev = NULL
        
        while temp is not NULL:
            if checkPrime(temp.data):
                hold = temp
            else:
                prev = temp
            
            temp = temp.next
            
            if temp is circularLinkedList.head:
                temp = NULL
            
            if hold is not NULL:
                if hold == circularLinkedList.head:
                    if circularLinkedList.tail == circularLinkedList.head:
                        circularLinkedList.tail = NULL
                    
                    circularLinkedList.head = temp
                else if circularLinkedList.tail == hold:
                    circularLinkedList.tail = prev
                else if prev is not NULL:
                    prev.next = temp
                
                if circularLinkedList.tail is not NULL:
                    circularLinkedList.tail.next = circularLinkedList.head
                
                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.

Program List

1) Delete all prime nodes of circular linked list in java 2) Delete all prime nodes of circular linked list in c++ 3) Delete all prime nodes of circular linked list in c 4) Delete all prime nodes of circular linked list in c# 5) Delete all prime nodes of circular linked list in php 6) Delete all prime nodes of circular linked list in python 7) Delete all prime nodes of circular linked list in swift 8) Delete all prime nodes of circular linked list in kotlin 9) Delete all prime nodes of circular linked list in ruby 10) Delete all prime nodes of circular linked list in scala 11) Delete all prime nodes of circular linked list in node js 12) Delete all prime nodes of circular linked list in typescript 13) Delete all prime nodes of circular linked list in vb.net 14) Delete all prime nodes of circular linked list in golang

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.