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
- Check if the linked list is empty. If it is, print a message and return.
- Initialize
temp
,hold
, andprev
pointers to traverse the list.hold
will store the node to be deleted, andprev
will store the previous node. - Traverse the list using the
temp
pointer. If the current node's data is prime, assign it tohold
; otherwise, assign it toprev
. - Move to the next node (
temp = temp.next
). - If the traversal reaches the end of the list or comes back to the head, update the
temp
pointer toNULL
. - If
hold
is notNULL
, 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 notNULL
, bypass the prime node by updatingprev.next
. - Connect the tail to the head to maintain the circular structure.
- If
- 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.
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.
New Comment