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:
- Initialize pointers
temp
andauxiliary
to the head node of the circular linked list. - Traverse the circular linked list using the
temp
pointer. - For each node, compute the sum of its digits using the
digitSum
function. - 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.
- Update the
- If the sum is even or zero, move the
auxiliary
pointer to the current node and continue to the next node. - 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
- If the circular linked list is empty, return.
- Initialize pointers
temp
andauxiliary
to the head node of the circular linked list. Also, initializepoint
to null. - Traverse the circular linked list using the
temp
pointer. - For each node, compute the sum of its digits using the
digitSum
function. - 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.
- Update the
- If the sum is even or zero, move the
auxiliary
pointer to the current node and continue to the next node. - 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.
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