Posted on by Kalkicode

# Delete all Even position nodes from circular linked list

In the problem of deleting all even position nodes from a circular linked list, we are working with a circular linked list data structure. The objective is to remove nodes that are at even positions (starting from index 0) from the circular linked list while maintaining its circular nature.

## Problem Statement

Given a circular linked list, we need to delete all nodes that are at even positions, considering the first node as position 0. After the deletion, the circular structure of the linked list should still be preserved.

## Example

Consider a circular linked list with the following elements: 12 -> 22 -> 32 -> 42 -> 52 -> 62 -> 72 -> 82. After deleting all even position nodes, the list becomes: 22 -> 42 -> 62 -> 82.

## Idea to Solve the Problem

To delete all even position nodes from a circular linked list, we need to iterate through the list and remove nodes at even positions. We'll handle various cases, such as when the list is empty, contains only one node, or has more than one node.

## Pseudocode

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

``````function deleteEvenPositionNodes(circularLinkedList):
return
# Only one element in the list
return

back.next = temp.next
temp = NULL
# Get next even position node
back = back.next
return
# Visit to next deleted node
temp = back.next

if back is not NULL:
# Connect last node to new head

## Algorithm Explanation

1. Check if the linked list is empty. If it is, print a message and return.
2. Check if the linked list has only one node. If it does, set the head to `NULL` and return.
3. Initialize `temp` and `back` pointers to traverse the list. `back` points to the previous node at an even position.
4. Traverse the list using the `temp` pointer, while also updating `back` and removing nodes at even positions.
5. After removing a node at an even position, update `back` to the next node, and continue the traversal.
6. If the traversal reaches the end of the list or comes back to the head, update the head and connect the last node to the new head to maintain the circular structure.

## Time Complexity

The time complexity of deleting all even position 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 position 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.

Categories
Relative Post