Skip to main content

Remove every k-th node of the linked list

The problem aims to remove every k-th node from a singly linked list. In this scenario, we are provided with a linked list, and our goal is to delete every k-th node, where k is a positive integer. The problem involves traversing the linked list and removing nodes at specific positions.

linked list before delete Every kth node linked list remove every 3rd element linked list remove every 2'nd element

Problem Description

Given a singly linked list and a positive integer k, we need to modify the linked list by removing every k-th node from it. The positions of the nodes to be removed are determined by the value of k, and the removal process should maintain the order of the remaining nodes.

Example

Consider the following linked list:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

If we choose k = 2, the modified linked list after removing every 2nd node will be:

1 -> 3 -> 5 -> 7

Idea to Solve the Problem

To solve this problem, we can traverse the linked list while keeping track of the current node's position. At every k-th position, we remove the current node and adjust the links to skip it. This process continues until we reach the end of the linked list.

Pseudocode

removeEveryKthNode(linkedList, k):
    if linkedList.head is NULL:
        return
    
    current = linkedList.head
    previous = NULL
    position = 1
    
    while current is not NULL:
        if position % k == 0:
            if previous is NULL:
                linkedList.head = current.next
            else:
                previous.next = current.next
            current = current.next
        else:
            previous = current
            current = current.next
        position = position + 1

Algorithm Explanation

  1. Start with the current pointer pointing to the head of the linked list, and initialize previous as NULL.
  2. Initialize a position variable to keep track of the current position.
  3. Traverse through the linked list using the current pointer: a. Check if the current position is a multiple of k. If yes, it's a k-th position, so remove the current node. b. If the position is not a multiple of k, update the previous pointer and move the current pointer to the next node.
  4. After each iteration, increment the position.
  5. If the position is a multiple of k, adjust the links to remove the current node.
  6. Continue these steps until the end of the linked list.

Code Solution

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. We traverse through each node once to remove the k-th nodes.





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