340. Cut Nth From End
A freight train is a chain of wagons, and the inspector reports that exactly one wagon is faulty: the one that is n-th counting from the rear, where the very last wagon is number 1. That wagon must be uncoupled and the two neighbours joined together.
Given the head of the chain and the integer n, remove the n-th node from the end and return the head of the resulting chain. It is guaranteed that 1 <= n <= length. If the chain has one node and it is removed, return an empty chain. The chain can hold up to 100,000 wagons and the length is not given, so try to do it in a single pass.
Example 1
- Input:
- head = [11,22,33,44,55,66], n = 2
- Output:
- [11,22,33,44,66]
- Explanation:
The 2nd wagon from the rear holds 55, so the result is 11, 22, 33, 44, 66.
Example 2
- Input:
- head = [9,4], n = 2
- Output:
- [4]
- Explanation:
The 2nd from the end is the head itself, leaving just 4.
Constraints
1 ≤ chain length ≤ 105
1 ≤ n ≤ chain length
-1000 ≤ node value ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(L)
- Space
- O(1)