Unsend the k-th newest message

Scenario

Kestrel Chat lets a sender unsend a recent message. The thread is stored as a chain of nodes from the oldest message to the newest, and each node holds a message id. The phone app knows how recent the message is: the newest message is number 1, the one before it is number 2, and so on.

The chain does not store its length. To unsend message number k, the server unlinks its node from the chain. It may be the oldest message, so the head itself can change. A thread holds up to 100,000 messages.

Your task

Write unsend_kth_newest(head, k).

head is the first node of the thread, the oldest message. It is never null. Each node's val is a message id.
k counts from the newest message: k = 1 is the newest, and k equals the length for the oldest.
Remove the k-th newest node from the chain and return the head of the thread that remains. Return null when no message remains.

The tests give head as the list of values from the head, and read your answer the same way.

Examples

Example 1 (traced)#

text2 lines

Input:  head = [301, 302, 303, 304, 305], k = 2
Output: [301, 302, 303, 305]

A placeholder node sits before 301. Both cursors start on it.

Step	lead	trail	What happens
start	placeholder	placeholder
lead moves k = 2 ahead	302	placeholder	the gap is now 2 nodes
both move	303	301	lead's next exists
both move	304	302	lead's next exists
both move	305	303	lead is on the newest message: stop
unlink	305	303	303 now points past 304, at 305

trail stops on the node before the k-th newest, which is the node whose pointer must change.

Example 2#

text2 lines

Input:  head = [301, 302, 303], k = 3
Output: [302, 303]

The third newest message is the oldest one, the head. trail stays on the placeholder, and the placeholder's next moves to 302.

Example 3#

text2 lines

Input:  head = [77], k = 1
Output: []

Constraints

1 ≤ number of nodes ≤ 10^5
1 ≤ node.val ≤ 10^9
1 ≤ k ≤ number of nodes

What does n ≤ 10^5 tell you?

One or two walks of 10^5 hops each are fast. Reading the chain like an array, with a fresh walk from the head for every position, is about n^2 / 2 hops: 5 × 10^9, which is too slow.

Counting the messages first and then walking to position n - k is correct and O(n). Two cursors kept k nodes apart find the same node in one walk.

Scenario

Your task

Write unsend_kth_newest(head, k).

head is the first node of the thread, the oldest message. It is never null. Each node's val is a message id.
k counts from the newest message: k = 1 is the newest, and k equals the length for the oldest.
Remove the k-th newest node from the chain and return the head of the thread that remains. Return null when no message remains.

The tests give head as the list of values from the head, and read your answer the same way.

Examples

Example 1 (traced)#

text2 lines

Input:  head = [301, 302, 303, 304, 305], k = 2
Output: [301, 302, 303, 305]

A placeholder node sits before 301. Both cursors start on it.

Step	lead	trail	What happens
start	placeholder	placeholder
lead moves k = 2 ahead	302	placeholder	the gap is now 2 nodes
both move	303	301	lead's next exists
both move	304	302	lead's next exists
both move	305	303	lead is on the newest message: stop
unlink	305	303	303 now points past 304, at 305

trail stops on the node before the k-th newest, which is the node whose pointer must change.

Example 2#

text2 lines

Input:  head = [301, 302, 303], k = 3
Output: [302, 303]

The third newest message is the oldest one, the head. trail stays on the placeholder, and the placeholder's next moves to 302.

Example 3#

text2 lines

Input:  head = [77], k = 1
Output: []

Constraints

1 ≤ number of nodes ≤ 10^5
1 ≤ node.val ≤ 10^9
1 ≤ k ≤ number of nodes

What does n ≤ 10^5 tell you?

One or two walks of 10^5 hops each are fast. Reading the chain like an array, with a fresh walk from the head for every position, is about n^2 / 2 hops: 5 × 10^9, which is too slow.

Counting the messages first and then walking to position n - k is correct and O(n). Two cursors kept k nodes apart find the same node in one walk.