Cut the K-th From the Tail
MediumLinked List
Problem
A printer queue is a singly linked list of jobs. A user cancels the job that sits k places from the end of the queue (the last job is 1st from the end).
Given the head and k, remove that node and return the head of the updated list. Do it in a single pass.
Example 1
- Input:
- head = [10, 20, 30, 40, 50], k = 2
- Output:
- [10, 20, 30, 50]
Counting from the end, 50 is 1st and 40 is 2nd, so 40 is removed.
Example 2
- Input:
- head = [1, 2], k = 2
- Output:
- [2]
The 2nd from the end is the head.
Constraints
- 1 ≤ number of nodes ≤ 10^4
- 1 ≤ k ≤ number of nodes
- 0 ≤ node.val ≤ 10^4
Hint
Show the first hint
Two passes are easy: count n, then remove the (n - k + 1)-th node. How do you avoid counting?
Walkthrough
How to approach it
01Clarify before coding
- Is k always valid? Yes, 1 ≤ k ≤ n.
- Can the head be removed? Yes, when k = n; a dummy node handles it.
- Can the list become empty? Yes, a single node with k = 1.
02Brute force
Walk once to count n, then walk n - k steps from a dummy and unlink the next node.
Cost: O(n) time and O(1) space, but two passes; the interviewer explicitly asked for one.
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.