Posted on by Kalkicode

# Remove all even parity nodes from a circular single linked list

In this problem, we are dealing with a circular singly linked list that contains integer values. The task is to remove nodes from the circular linked list that have an even parity of set bits in their binary representation.

## 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 binary representation has an even number of set bits (bits with a value of 1) 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 -> 14 -> 27 -> 19 -> 1 -> 18 -> 3 (back to the start)``

After removing nodes with even parity of set bits, the circular linked list should look like this:

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

## Idea to Solve

To solve this problem, we can follow these steps:

1. Traverse the circular linked list using the `temp` pointer.
2. For each node, calculate the number of set bits (bits with a value of 1) in its binary representation using the `coutSetBit` function.
3. Check if the count of set bits is even. If it is, mark the node for removal.
4. Traverse the circular linked list again using the `temp` pointer, this time with the objective of removing the marked nodes.
5. For each marked node, remove it from the list while maintaining the circular structure.

## Pseudocode

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

while temp is not null:
if coutSetBit(temp.data) is even:
auxiliary = temp
temp = temp.next
if auxiliary is tail:
// Removing a single node
tail = null
temp = null
else:
tail.next = temp
else if auxiliary is tail:
if point is not null:
// Remove last node
tail = point
else:
if point is not null:
// Remove intermediate node
point.next = temp
auxiliary = null
else:
point = temp
temp = temp.next
// Stop the process
temp = null``````

## Algorithm Explanation

1. Traverse the circular linked list using the `temp` pointer.
2. Calculate the number of set bits in the binary representation of the current node's data using the `coutSetBit` function.
3. Check if the count of set bits is even. If it is, mark the current node for removal.
4. Depending on whether the current node (`auxiliary`) is the head, tail, or an intermediate node, remove the node from the list while maintaining the circular structure.
5. If the current node's data doesn't have an even number of set bits, update the `point` pointer to `temp` and move `temp` to the next node.
6. If `temp` has reached back to the head, terminate the loop by setting `temp` to null.

## Time Complexity

1. In the `coutSetBit` function, the number of set bits is counted using bitwise operations. This operation is executed in constant time, regardless of the input value. Thus, the time complexity of the `coutSetBit` function is O(1).

2. In the `removeNode` function, we traverse the circular linked list twice. The first traversal identifies nodes with even parity of set bits. The second traversal removes these nodes while maintaining the circular structure. Both traversals have a time complexity of O(N), where N is the number of nodes in the linked list.

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

Categories
Relative Post