Posted on by Kalkicode
Code Circular Linked List

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():
    if head is null:
        return
    initialize temp as head
    initialize auxiliary as head
    initialize point as null
    
    while temp is not null:
        if coutSetBit(temp.data) is even:
            auxiliary = temp
            temp = temp.next
            if auxiliary is head:
                // Remove head node
                if auxiliary is tail:
                    // Removing a single node
                    tail = null
                    head = null
                    temp = null
                else:
                    head = temp
                    tail.next = temp
            else if auxiliary is tail:
                if point is not null:
                    // Remove last node
                    point.next = head
                tail = point
            else:
                if point is not null:
                    // Remove intermediate node
                    point.next = temp
            auxiliary = null
        else:
            point = temp
            temp = temp.next
            if temp is head:
                // 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.

Code Solution

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.

New Comment