Delete Every Kth Node in a Linked List
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.
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:
k is 1, all nodes should be deleted, resulting in an empty list (return null).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:
ListNode object representing the head of the modified linked list after deleting every Kth node. If the list becomes empty, return null.head = null) should result in an empty list (null).k will always be a positive integer (k >= 1).Examples
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.
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.
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.
Example 4
Input:
head = [], k = 2
Output:
[]
Note:
An empty list remains empty.
Constraints
1 <= k <= 10^5.val of nodes will be between -1000 and 1000.k=1, empty lists, and lists shorter than k.next pointers to bypass nodes.Loading editor...