# Remove all fibonacci nodes from a circular single linked list

In this problem, we are working with a circular singly linked list containing integer values. The task is to remove all nodes from the circular linked list whose data values are Fibonacci numbers.

## Problem Statement and Description

The problem requires us to remove nodes from the circular linked list based on a specific condition. We need to identify the nodes whose data values are Fibonacci numbers and remove them while maintaining the circular structure of the linked list.

## Example

Let's understand the problem with an example. Consider the following circular linked list:

``Original Circular Linked List: 3 -> 12 -> 32 -> 1 -> 14 -> 0 -> 27 -> 13 -> 89 -> 3 (back to the start)``

After removing the Fibonacci nodes, the circular linked list should look like this:

``Modified Circular Linked List: 12 -> 32 -> 14 -> 27 -> 12 (back to the start)``

## Idea to Solve

To solve this problem, we can follow these steps:

1. Traverse the circular linked list to find the maximum value present in the nodes. This value will help us determine the range of Fibonacci numbers we need to generate.
2. Generate a HashSet containing Fibonacci numbers up to the maximum value found in step 1. This HashSet will allow us to quickly check if a node's data is a Fibonacci number.
3. Traverse the circular linked list again and for each node, check if its data value is in the HashSet of Fibonacci numbers. If it is, remove the node from the list while maintaining the circular structure.

## Pseudocode

``````removeFibonacciNode():
return
initialize record as an empty HashSet

// Find the maximum node value
while temp is not null and temp is not head:
if max < temp.data:
max = temp.data
temp = temp.next

// Generate Fibonacci numbers up to max
fibNumber(record, max)

initialize point as null

while temp is not null:
if data of temp is in record:
auxiliary = temp
temp = temp.next
if auxiliary is tail:
// Removing a single node
tail = null
temp = null
point = null
else:
tail.next = temp
else if auxiliary is tail:
// Remove last node
if point is not null:
tail = point
else:
// Remove intermediate node
if point is not null:
point.next = temp
auxiliary = null
else:
point = temp
temp = temp.next
temp = null``````

## Algorithm Explanation

1. Traverse the circular linked list to find the maximum value among the nodes. This value will be used to generate Fibonacci numbers.
2. Generate a HashSet called `record` containing Fibonacci numbers up to the maximum value using the `fibNumber` function.
3. Traverse the circular linked list again using the `temp` pointer.
4. Check if the data value of the current node (`temp.data`) is present in the `record` HashSet.
5. If it is in the `record`, store the reference to the current node (`temp`) in the `auxiliary` pointer and move `temp` to the next node.
6. Depending on whether `auxiliary` is the head, tail, or an intermediate node, remove the node from the list while maintaining the circular structure.
7. If the current node's data is not a Fibonacci number, update the `point` pointer to `temp` and move `temp` to the next node.
8. If `temp` has reached back to the head, terminate the loop by setting `temp` to null.

## Time Complexity

1. In the `fibNumber` function, we generate Fibonacci numbers up to a maximum value. The number of Fibonacci numbers generated depends on the maximum value. Let's denote this maximum value as N. Generating Fibonacci numbers has a time complexity of O(N), and inserting them into the HashSet also has a time complexity of O(N). Thus, the overall time complexity of the `fibNumber` function is O(N).

2. In the `removeFibonacciNode` function, we traverse the circular linked list twice. The first traversal finds the maximum value among the nodes, which takes O(N) time. The second traversal removes nodes based on Fibonacci numbers, which also takes O(N) time due to the while loop. The operations within the loop, such as updating pointers, are constant-time operations. Therefore, the overall time complexity of the `removeFibonacciNode` function is O(N).

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