Posted on by Kalkicode

# 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.

## 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

``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):
return

previous = NULL
position = 1

while current is not NULL:
if position % k == 0:
if previous is NULL:
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.

## 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.

Categories
Relative Post