Drop Every K-th Node
EasyLinked List
Problem
A sampling tool thins a stream stored as a singly linked list: counting positions from 1, every node whose position is a multiple of k is discarded.
Given the head and k, remove the nodes at positions k, 2k, 3k, … of the original list and return the head of what remains.
Example 1
- Input:
- head = [1, 2, 3, 4, 5, 6, 7], k = 3
- Output:
- [1, 2, 4, 5, 7]
Positions 3 and 6 (values 3 and 6) are removed.
Example 2
- Input:
- head = [4, 8], k = 1
- Output:
- []
Every position is a multiple of 1.
Constraints
- 0 ≤ number of nodes ≤ 10^4
- 1 ≤ k ≤ 10^4
- -10^4 ≤ node.val ≤ 10^4
Hint
Show the first hint
Positions refer to the original list, so count every node you pass, including the ones you remove.
Walkthrough
How to approach it
01Clarify before coding
- Are positions those of the original list or recomputed after each removal? Original positions.
- What if k is larger than the list? Nothing is removed.
- What if k = 1? Every node is removed.
02Brute force
Copy the values whose position is not a multiple of k into an array and build a new list.
Cost: O(n) time and O(n) extra space for new nodes.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.