Posted on by Kalkicode
Code Circular Linked List

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.

Before Remove kth node After Remove kth node

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):
    if circularLinkedList.head is NULL:
        return
    if k <= 0:
        return
    
    counter = 0
    temp = circularLinkedList.head
    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
        
        if temp is circularLinkedList.head:
            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.

Code Solution

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.

New Comment