Frontend School

Delete Every Kth Node in a Linked List

DSA
easy

Delete Every Kth Node in a Linked List

Easy
Linked List

Overview

In the context of managing vehicle data logs or sensor readings, sometimes it's necessary to downsample data to reduce storage or processing load. For sequential data represented as a linked list, one common downsampling strategy is to remove elements at regular intervals. This problem asks you to implement such a strategy, specifically deleting every Kth node from a given singly linked list.

What you need to do / Task

You are tasked with implementing a function deleteEveryKthNode that takes the head of a singly linked list and an integer k as input. The function should modify the list in-place by deleting every Kth node, starting from the first Kth node.

Specifically:

  1. Identify the 1st, 2nd, 3rd, ..., Kth node. This Kth node should be deleted.
  2. Continue traversing the list, counting from the node after the deleted node. The next Kth node encountered should also be deleted.
  3. Repeat this process until the end of the list is reached.
  4. If k is 1, all nodes should be deleted, resulting in an empty list (return null).
  5. The original relative order of the remaining nodes must be preserved.

Input & output

Input:

  • head: A ListNode object representing the head of a singly linked list. Each ListNode has a val (number) and a next (ListNode | null) property.
  • k: A positive integer representing the interval at which nodes should be deleted.

Output:

  • A ListNode object representing the head of the modified linked list after deleting every Kth node. If the list becomes empty, return null.

Clarifications

  • An empty input list (head = null) should result in an empty list (null).
  • k will always be a positive integer (k >= 1).
  • The list can contain anywhere from 0 to 10^5 nodes.

Examples

1

Example 1

Input:

head = [1,2,3,4,5,6,7,8], k = 3

Output:

[1,2,4,5,7,8]

Note:

The 3rd node (value 3) is deleted. Then counting from 4, the 3rd node is 6 (value 6), which is deleted. Then counting from 7, the list ends before another 3rd node.

2

Example 2

Input:

head = [1,2,3,4,5], k = 1

Output:

[]

Note:

When k=1, every node is the Kth node, so all nodes are deleted. The list becomes empty.

3

Example 3

Input:

head = [1,2], k = 5

Output:

[1,2]

Note:

The list has only 2 nodes, which is less than k=5. No node is the 5th node, so no nodes are deleted.

4

Example 4

Input:

head = [], k = 2

Output:

[]

Note:

An empty list remains empty.

Constraints

Constraints & assumptions

  • The number of nodes in the list will be between 0 and 10^5.
  • 1 <= k <= 10^5.
  • The val of nodes will be between -1000 and 1000.
  • The solution should ideally operate in O(N) time complexity, where N is the number of nodes in the list.
  • The solution should ideally operate in O(1) space complexity, meaning no auxiliary data structures that grow with N.
  • The modification should be done in-place.

What interviewers evaluate

  • Correctness: The solution correctly identifies and deletes every Kth node, handling edge cases like k=1, empty lists, and lists shorter than k.
  • Efficiency: The algorithm demonstrates optimal time and space complexity for the given constraints.
  • Code Quality: The code is well-structured, readable, and follows good programming practices (e.g., clear variable names, appropriate comments).
  • Pointer Manipulation: Demonstrates a solid understanding of linked list manipulation, especially handling next pointers to bypass nodes.

Loading editor...