Remove Every k-th Node of a Linked List — Problem & Solution
Remove Every k-th Node of a Linked List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Remove Every k-th Node of a Linked List is an easy coding problem on simulation, asked in Amazon interviews.
- Difficulty: Easy
- Topics: Simulation
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the head of a singly linked list and an integer k, delete every k-th node of the list — the k-th, the 2k-th, the 3k-th node and so on, counting positions from 1 in the original list — and return the head of what remains.
If k is larger than the length of the list nothing is deleted; if k is 1 every node is deleted and the answer is the empty list.
Example 1
Input: head = [1,2,3,4,5,6,7,8], k = 3
Output: [1,2,4,5,7,8]
Explanation: The 3rd and 6th nodes (values 3 and 6) are removed.
Example 2
Input: head = [1,2,3,4,5,6,7,8,9,10], k = 2
Output: [1,3,5,7,9]
Example 3
Input: head = [4,9], k = 1
Output: []
Explanation: With k = 1 every position is a multiple of k.
Constraints
1 <= number of nodes <= 10^51 <= Node.val <= 10^61 <= k <= 10^5
Hints for Remove Every k-th Node of a Linked List
Hint 1
A node is deleted exactly when its 1-based position is a multiple of
k.Hint 2
Walk the list once with a counter, keeping a pointer to the node before the current one so it can be unlinked.
Hint 3
A dummy node in front of the head makes deleting the first node (k = 1) no different from deleting any other.
How to solve Remove Every k-th Node of a Linked List
Positions are fixed by the original list, so a single walk with a counter decides every node: a position that is a multiple of k is unlinked, every other node is kept.
Approach
- Put a dummy node before
headand setprev = dummy,count = 0. - While
prev.nextexists, increasecount; ifcount % k == 0, unlink the node withprev.next = prev.next.nextand stay put; otherwise moveprevforward. - Return
dummy.next.
Why it works
count is incremented exactly once for every node of the original list, in order, whether the node is kept or removed — so it always equals that node's original position, and the test count % k == 0 removes exactly the multiples of k.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Do not advance
prevafter unlinking — its new successor still has to be counted. - k = 1 empties the list; without a dummy node the head needs special handling.
- Counting positions in the shrinking list instead of the original one deletes the wrong nodes.
Reference solution
Python
from typing import Optional
def deleteK(head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(0, head)
prev = dummy
count = 0
while prev.next:
count += 1
if count % k == 0:
prev.next = prev.next.next
else:
prev = prev.next
return dummy.nextJava
public static ListNode deleteK(ListNode head, int k) {
ListNode dummy = new ListNode(0, head), prev = dummy;
int count = 0;
while (prev.next != null) {
count++;
if (count % k == 0) prev.next = prev.next.next;
else prev = prev.next;
}
return dummy.next;
}C++
ListNode* deleteK(ListNode* head, int k) {
ListNode dummy(0, head);
ListNode* prev = &dummy;
int count = 0;
while (prev->next) {
count++;
if (count % k == 0) prev->next = prev->next->next;
else prev = prev->next;
}
return dummy.next;
}JavaScript
var deleteK = function(head, k) {
var dummy = new ListNode(0, head), prev = dummy, count = 0;
while (prev.next !== null) {
count++;
if (count % k === 0) prev.next = prev.next.next;
else prev = prev.next;
}
return dummy.next;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.