# Remove all the Odd digit sum nodes from a circular linked list

The Remove all the Odd Digit Sum Nodes from a Circular Linked List problem involves removing nodes from a circular linked list based on whether the sum of the digits in their data is odd or even. If the sum of digits is odd, the node is removed from the list; otherwise, it is retained. This problem highlights the process of manipulating circular linked lists and evaluating digit sums.

## Problem Statement

Given a circular linked list, the problem is to remove all nodes from the list whose data has an odd digit sum.

## Example

Linked List: 131 -> 12 -> 33 -> 10 -> 143 -> 91 -> 27 -> 125 -> 89

After removing nodes with odd digit sum:

Result: 33 -> 143 -> 91 -> 125

``````Node   Digit Sum    Odd
----- -----------  --------
131   [1+3+1] 5     Yes
12    [1+2]   3     Yes
33    [3+3]   6     No
10    [10]    1     Yes
143   [1+4+3] 8     No
91    [9+1]   10    No
27    [2+7]   9     Yes
125   [1+2+5] 8     No
89    [8+9]   17    Yes
--------------------------
Result
------
33 → 143 → 91 → 125 ┐
└-----------------⤶``````

## Idea to Solve the Problem

To solve the problem of removing nodes with odd digit sums from a circular linked list, follow these steps:

1. Initialize pointers `temp` and `auxiliary` to the head node of the circular linked list.
2. Traverse the circular linked list using the `temp` pointer.
3. For each node, compute the sum of its digits using the `digitSum` function.
4. If the sum is odd, remove the current node using the following logic:
• Update the `auxiliary` pointer to point to the next node.
• Update the next pointer of the previous node to skip the current node.
• If the current node is the head node, update the head pointer to the next node.
• If the current node is the tail node, update the tail pointer to the previous node.
• Free the memory allocated for the removed node.
5. If the sum is even or zero, move the `auxiliary` pointer to the current node and continue to the next node.
6. Continue this process until the traversal completes and the `temp` pointer points back to the head node.

## Pseudocode

``````function removeOddDigitSumNode():
return
point = null
while temp is not null:
sum = digitSum(temp.data)
if sum % 2 is not equal to 0:
auxiliary = temp
temp = temp.next
if auxiliary is equal to head:
if auxiliary is equal to tail:
tail = null
temp = null
point = null
else:
tail.next = temp
else if auxiliary is equal to 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
if temp is equal to head:
temp = null``````

## Algorithm Explanation

1. If the circular linked list is empty, return.
2. Initialize pointers `temp` and `auxiliary` to the head node of the circular linked list. Also, initialize `point` to null.
3. Traverse the circular linked list using the `temp` pointer.
4. For each node, compute the sum of its digits using the `digitSum` function.
5. If the sum is odd, remove the current node:
• Update the `auxiliary` pointer to point to the next node.
• Update the next pointer of the previous node to skip the current node.
• If the current node is the head node, update the head pointer to the next node.
• If the current node is the tail node, update the tail pointer to the previous node.
• Free the memory allocated for the removed node.
6. If the sum is even or zero, move the `auxiliary` pointer to the current node and continue to the next node.
7. Continue this process until the traversal completes and the `temp` pointer points back to the head node.

## Time Complexity

The time complexity of removing nodes with odd digit sums from a circular linked list is O(n), where n is the number of nodes in the linked list. In the worst case, the algorithm may need to traverse all nodes in the circular linked list to determine whether the digit sum is odd or even.

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