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

Consider the circular linked list:

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():
    if head is null:
        return
    temp = head
    auxiliary = head
    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
                    head = null
                    temp = null
                    point = null
                else:
                    head = temp
                    tail.next = temp
            else if auxiliary is equal to tail:
                if point is not null:
                    point.next = head
                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.

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

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.