Skip to main content

Delete all odd nodes of a circular linked list

In this problem, we are dealing with a circular linked list data structure. A circular linked list is a type of linked list where the last node's next pointer points back to the first node instead of being null. The problem requires us to delete all the nodes from the circular linked list that contain odd values in their data fields.

Problem Statement and Description

We have a circular linked list containing integer values. Our task is to remove all nodes with odd values from this circular linked list while keeping the list's circular structure intact. We want to achieve this by modifying the links (pointers) between nodes.

Example

Let's understand the problem with an example. Consider the following circular linked list:

Original Circular Linked List: 3 -> 12 -> 32 -> 1 -> 14 -> 27 -> 0 -> 13 -> 89 -> 3 (back to the start)

After removing the odd nodes, the circular linked list should look like this:

Modified Circular Linked List: 12 -> 32 -> 14 -> 0 -> 12 (back to the start)

Idea to Solve

To solve this problem, we need to traverse the circular linked list while maintaining a reference to the previous node (point) and the current node. We'll iterate through the list and check if the current node's data is odd. If it is odd, we'll update the pointers to remove the current node from the list. If it's not odd, we'll continue traversing.

Pseudocode

removeOddNode():
    if head is null:
        return
    initialize temp as head
    initialize point as null
    initialize auxiliary as head
    
    while temp is not null:
        if temp.data is odd:
            auxiliary = temp
            temp = temp.next
            if auxiliary is head:
                if auxiliary is tail:
                    // Removing the only node
                    tail = null
                    head = null
                    temp = null
                    point = null
                else:
                    head = temp
                    tail.next = temp
            else if auxiliary is 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 head:
                temp = null

Algorithm Explanation

  1. Check if the linked list is empty (head is null). If it is, there's nothing to remove, so return.
  2. Initialize the necessary pointers: temp to traverse the list, point to keep track of the previous node, and auxiliary to assist in removing nodes.
  3. Start iterating through the list using the temp pointer.
  4. Check if the data of the current node (temp.data) is odd. Use bitwise AND with 1 to check the least significant bit.
  5. If the data is odd, store the reference to the current node (temp) in the auxiliary pointer and move temp to the next node.
  6. Check if the auxiliary node is the head node. If it is, handle removing the head node scenario.
    • If it's the only node in the list (also tail), set both head and tail to null, and clear the pointers.
    • If it's not the only node, update head and make tail.next point to the new head.
  7. If auxiliary is the tail node, handle removing the tail node scenario.
    • If point (previous node) is not null, update point.next to point to the head, maintaining the circular structure.
    • Update tail to the previous node (point).
  8. If auxiliary is neither the head nor the tail, handle removing an intermediate node.
    • Update point.next to point to the next node (temp).
  9. Set auxiliary to null to prevent accidental access.
  10. If the current node's data is not odd, it's an even node. Update the point pointer to temp and move temp to the next node.
  11. Check if temp has reached back to the head, indicating completion of one loop through the circular list. In this case, set temp to null to terminate the loop.

Code Solution

Time Complexity

The time complexity of the removeOddNode function is O(N), where N is the number of nodes in the circular linked list. This is because we are traversing through all the nodes once to identify and remove odd nodes. The operations within the loop, such as updating pointers, are constant-time operations.





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