.png)
Remove Every K-th Node in a Linked List
Problem Statement
You are given a singly linked list and an integer K. Your task is to remove every K-th node from the linked list.
Key Rule
- Counting starts from the first node
- Every K-th node must be deleted
- The remaining nodes should preserve their original order
Understanding the Problem Clearly
Let us understand the problem using an example.
Example 1
Input Linked List:
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
K = 3
Deletion Process
- Remove 3rd node → 3
- Remove 6th node → 6
- Remove 9th node → does not exist
Output Linked List
1 → 2 → 4 → 5 → 7 → 8 → NULL
Important Edge Cases
Before jumping into solutions, we must handle edge cases:
- K = 1
- Every node must be deleted
- Output will be an empty list
- K > Length of Linked List
- No node is deleted
- List remains unchanged
- Empty Linked List
- Nothing to delete
- Linked List with Single Node
- Deleted only if K = 1
Approach 1: Iterative Counting Approach (Most Common)
Idea
We traverse the linked list while maintaining:
- A counter to track node positions
- A previous pointer to reconnect nodes after deletion
Whenever the counter becomes a multiple of K, the current node is removed.
Algorithm
- If head is NULL, return head.
- If K == 1, delete the entire list.
- Initialize:
- current = head
- previous = NULL
- count = 1
- Traverse the list:
- If count % K == 0:
- Delete current
- Update previous.next
- Else:
- Move previous forward
- Increment count
- If count % K == 0:
- Return updated head.
Time and Space Complexity
- Time Complexity: O(n)
- Space Complexity: O(1)
Implementation
C Implementation
// while running your code please replace " of "stdio.h" with < and > respectively
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
// Create new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Insert at end
struct Node* insertEnd(struct Node* head, int data) {
struct Node* newNode = createNode(data);
if (head == NULL)
return newNode;
struct Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
return head;
}
// Display list
void display(struct Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
// Remove every K-th node
struct Node* removeKthNode(struct Node* head, int k) {
if (head == NULL)
return NULL;
if (k == 1)
return NULL;
struct Node* current = head;
struct Node* previous = NULL;
int count = 1;
while (current != NULL) {
if (count % k == 0) {
struct Node* temp = current;
previous->next = current->next;
current = current->next;
free(temp);
} else {
previous = current;
current = current->next;
}
count++;
}
return head;
}
int main() {
struct Node* head = NULL;
// Input: 10 → 20 → 30 → 40 → 50
int arr[] = {10, 20, 30, 40, 50};
for (int i = 0; i < 5; i++) {
head = insertEnd(head, arr[i]);
}
printf("Original List:\n");
display(head);
int k = 2;
head = removeKthNode(head, k);
printf("\nAfter removing every %d-th node:\n", k);
display(head);
return 0;
}Java Implementation
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class RemoveKthNode {
static Node removeKthNode(Node head, int k) {
if (head == null)
return null;
if (k == 1)
return null;
Node current = head;
Node previous = null;
int count = 1;
while (current != null) {
if (count % k == 0) {
previous.next = current.next;
} else {
previous = current;
}
current = current.next;
count++;
}
return head;
}
}
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def remove_kth_node(head, k):
if head is None:
return None
if k == 1:
return None
current = head
previous = None
count = 1
while current:
if count % k == 0:
previous.next = current.next
else:
previous = current
current = current.next
count += 1
return head
Dry Run Example
Input
List: 10 → 20 → 30 → 40 → 50 → NULL
K = 2
Step-by-Step
| Node | Count | Action |
|---|---|---|
| 10 | 1 | Keep |
| 20 | 2 | Delete |
| 30 | 3 | Keep |
| 40 | 4 | Delete |
| 50 | 5 | Keep |
Output
10 → 30 → 50 → NULL
Common Mistakes Students Make
- Forgetting to handle K = 1
- Losing reference to head
- Incorrect pointer updates
- Not freeing memory (C/C++)
- Infinite loop due to incorrect traversal
Alternative Approach (Using Length)
Idea
- Calculate the length first
- Delete nodes at positions K, 2K, 3K...
Less efficient due to two traversals
Used mainly for conceptual understanding
Interview Tips
- Interviewers expect O(n) time and O(1) space
- Always mention edge cases
- Explain pointer movement clearly
- Dry run is more important than code
10. Summary
- Removing every K-th node requires careful pointer manipulation
- Iterative approach is optimal
- Handling K = 1 is critical
- This problem strengthens traversal and deletion concepts
Practice Variations
Try solving:
- Remove every alternate node
- Remove nodes at prime positions
- Remove nodes with even values
- Remove nodes greater than X
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
