Skip to main content

Delete all the even nodes of a Circular Linked List

In the problem of deleting all even nodes from a circular linked list, we are dealing with a circular linked list data structure. The objective is to remove nodes from the list that contain even values, while maintaining the circular nature of the linked list.

Problem Statement

Given a circular linked list, we need to delete all nodes that contain even values. After the deletion, the circular structure of the linked list should be preserved.

Example

Consider a circular linked list with the following elements: 12 -> 21 -> 30 -> 41 -> 53 -> 60 -> 79 -> 88. After deleting all even nodes, the list becomes: 21 -> 41 -> 53 -> 79.

Idea to Solve the Problem

Before Remove even key nodes after Remove even key nodes

To delete all even nodes from a circular linked list, we need to iterate through the list and identify nodes with even values. For each even node, we'll perform the deletion while maintaining the circular structure.

Pseudocode

Here's the pseudocode to delete all even nodes from a circular linked list:

function deleteEvenNodes(circularLinkedList):
    if circularLinkedList.head is NULL:
        return
    temp = circularLinkedList.head.next
    auxiliary = circularLinkedList.head
    hold = NULL

    while temp is not circularLinkedList.head:
        hold = temp
        temp = temp.next
        if hold.data is even:
            auxiliary.next = temp
            hold = NULL
        else:
            auxiliary = hold

    if circularLinkedList.head.data is even:
        temp = circularLinkedList.head
        if circularLinkedList.head.next is circularLinkedList.head:
            circularLinkedList.head = NULL
        else:
            circularLinkedList.head = circularLinkedList.head.next
            auxiliary.next = circularLinkedList.head
        temp = NULL

Algorithm Explanation

  1. Check if the linked list is empty. If it is, return.
  2. Initialize temp, auxiliary, and hold pointers for traversal.
  3. Traverse the list using the temp pointer. If the current node's data is even, assign it to hold; otherwise, assign it to auxiliary.
  4. Move to the next node (temp = temp.next).
  5. If the traversal reaches the end of the list, update the temp pointer to circularLinkedList.head.
  6. If hold is not NULL, perform the deletion by updating the auxiliary.next to temp and freeing memory.
  7. If the head node's data is even, perform the deletion by updating the head and auxiliary.next pointers, and freeing memory.

Code Solution

Time Complexity

The time complexity of deleting all even nodes from a circular linked list is O(n), where n is the number of nodes in the circular linked list. This is because we need to traverse the entire list to identify and remove even nodes. The space complexity is O(1) as we are using only a constant amount of extra space for pointers.





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