Posted on by Kalkicode

# Delete every Kth node from circular linked list

The problem at hand involves deleting every k-th node from a circular linked list, while preserving the circular structure of the list. In a circular linked list, the last node's next pointer points back to the first node, creating a closed loop.

## Problem Statement

Given a circular linked list, we need to delete every k-th node from the list while keeping the circular structure intact.

## Example

Consider a circular linked list with the following elements: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8. If k is 2, after deleting every 2nd node, the list becomes: 1 -> 3 -> 5 -> 7.

## Idea to Solve the Problem

To delete every k-th node from the circular linked list, we can traverse the list while keeping track of the current position. If the current position is a multiple of k, we delete the node. We'll need to update pointers to maintain the circular structure.

## Pseudocode

Here's the pseudocode to delete every k-th node from a circular linked list:

``````function deleteKthNodes(circularLinkedList, k):
return
if k <= 0:
return

counter = 0
hold = NULL
prev = NULL

while temp is not NULL:
counter = counter + 1
if counter % k == 0:
hold = temp
else:
prev = temp

temp = temp.next

if hold is not NULL:
if prev is not NULL:
prev.next = temp
hold = NULL

return``````

## Algorithm Explanation

1. Check if the linked list is empty or if k is less than or equal to 0. If any of these conditions are met, return.
2. Initialize `counter` to keep track of the current position, `temp` to traverse the list, and `hold` to store the node to be deleted.
3. Traverse the list using the `temp` pointer. If the current position is a multiple of k, update the `hold` pointer.
4. If the current position is not a multiple of k, update the `prev` pointer.
5. Move to the next node (`temp = temp.next`).
6. If `hold` is not NULL, it means we need to delete a node. Update the `prev.next` pointer to skip the node to be deleted.
7. If `temp` reaches the head of the circular list, return.

## Time Complexity

The time complexity of deleting every k-th node from a circular linked list is O(n), where n is the number of nodes in the circular linked list. Since we need to traverse the entire list once, the time complexity is linear. 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