Remove Every k-th Node of a Linked List

Easy
1999.

Remove Every k-th Node of a Linked List

EasyLinked ListSimulationAmazon

Remove Every k-th Node of a Linked List is an easy coding problem on simulation, asked in Amazon interviews.

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^5
  • 1 <= Node.val <= 10^6
  • 1 <= k <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var deleteK = function(head, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 1 <= Node.val <= 10^6
  • 1 <= k <= 10^5

Hints for Remove Every k-th Node of a Linked List

  1. Hint 1

    A node is deleted exactly when its 1-based position is a multiple of k.

  2. Hint 2

    Walk the list once with a counter, keeping a pointer to the node before the current one so it can be unlinked.

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

  1. Put a dummy node before head and set prev = dummy, count = 0.
  2. While prev.next exists, increase count; if count % k == 0, unlink the node with prev.next = prev.next.next and stay put; otherwise move prev forward.
  3. 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 prev after 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.next

Java

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.

All 137 simulation problems · the whole catalogue