# Delete all odd nodes of a circular linked list

In this problem, we are dealing with a circular linked list data structure. A circular linked list is a type of linked list where the last node's next pointer points back to the first node instead of being null. The problem requires us to delete all the nodes from the circular linked list that contain odd values in their data fields.

## Problem Statement and Description

We have a circular linked list containing integer values. Our task is to remove all nodes with odd values from this circular linked list while keeping the list's circular structure intact. We want to achieve this by modifying the links (pointers) between nodes.

## Example

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

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

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

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

## Idea to Solve

To solve this problem, we need to traverse the circular linked list while maintaining a reference to the previous node (point) and the current node. We'll iterate through the list and check if the current node's data is odd. If it is odd, we'll update the pointers to remove the current node from the list. If it's not odd, we'll continue traversing.

## Pseudocode

``````removeOddNode():
return
initialize point as null

while temp is not null:
if temp.data is odd:
auxiliary = temp
temp = temp.next
if auxiliary is tail:
// Removing the only node
tail = null
temp = null
point = null
else:
tail.next = temp
else if auxiliary is tail:
if point is not null:
tail = point
else:
if point is not null:
point.next = temp
auxiliary = null
else:
point = temp
temp = temp.next
temp = null``````

## Algorithm Explanation

1. Check if the linked list is empty (head is null). If it is, there's nothing to remove, so return.
2. Initialize the necessary pointers: `temp` to traverse the list, `point` to keep track of the previous node, and `auxiliary` to assist in removing nodes.
3. Start iterating through the list using the `temp` pointer.
4. Check if the data of the current node (`temp.data`) is odd. Use bitwise AND with 1 to check the least significant bit.
5. If the data is odd, store the reference to the current node (`temp`) in the `auxiliary` pointer and move `temp` to the next node.
6. Check if the `auxiliary` node is the head node. If it is, handle removing the head node scenario.
• If it's the only node in the list (also tail), set both `head` and `tail` to null, and clear the pointers.
• If it's not the only node, update `head` and make `tail.next` point to the new head.
7. If `auxiliary` is the tail node, handle removing the tail node scenario.
• If `point` (previous node) is not null, update `point.next` to point to the head, maintaining the circular structure.
• Update `tail` to the previous node (`point`).
8. If `auxiliary` is neither the head nor the tail, handle removing an intermediate node.
• Update `point.next` to point to the next node (`temp`).
9. Set `auxiliary` to null to prevent accidental access.
10. If the current node's data is not odd, it's an even node. Update the `point` pointer to `temp` and move `temp` to the next node.
11. Check if `temp` has reached back to the head, indicating completion of one loop through the circular list. In this case, set `temp` to null to terminate the loop.

## Time Complexity

The time complexity of the `removeOddNode` function is O(N), where N is the number of nodes in the circular linked list. This is because we are traversing through all the nodes once to identify and remove odd nodes. The operations within the loop, such as updating pointers, are constant-time operations.

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