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):
if circularLinkedList.head is NULL:
print "Empty linked list"
return
else if circularLinkedList.head.next is circularLinkedList.head:
# Only one element in the list
circularLinkedList.head = NULL
return
temp = circularLinkedList.head.next.next
back = circularLinkedList.head.next
while temp is not NULL and temp is not circularLinkedList.head:
# Unlink deleted node
back.next = temp.next
temp = NULL
# Get next even position node
back = back.next
if back is circularLinkedList.head:
return
# Visit to next deleted node
temp = back.next
# Set new head
circularLinkedList.head = circularLinkedList.head.next
if back is not NULL:
# Connect last node to new head
back.next = circularLinkedList.head
Algorithm Explanation
- Check if the linked list is empty. If it is, print a message and return.
- Check if the linked list has only one node. If it does, set the head to
NULL
and return. - Initialize
temp
andback
pointers to traverse the list.back
points to the previous node at an even position. - Traverse the list using the
temp
pointer, while also updatingback
and removing nodes at even positions. - After removing a node at an even position, update
back
to the next node, and continue the traversal. - 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.
Program List
-
1) Delete all even position nodes from circular linked list in c++
2) Delete all even position nodes from circular linked list in java
3) Delete all even position nodes from circular linked list in c
4) Delete all even position nodes from circular linked list in golang
5) Delete all even position nodes from circular linked list in c#
6) Delete all even position nodes from circular linked list in vb.net
7) Delete all even position nodes from circular linked list in php
8) Delete all even position nodes from circular linked list in node js
9) Delete all even position nodes from circular linked list in typescript
10) Delete all even position nodes from circular linked list in python
11) Delete all even position nodes from circular linked list in ruby
12) Delete all even position nodes from circular linked list in scala
13) Delete all even position nodes from circular linked list in swift
14) Delete all even position nodes from circular linked list in kotlin
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.
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