Linked Lists Fast and slow pointers
290. Remove Nth Node From End of List
You are given head, the first node of a singly linked list, and an integer n. Delete the node that is
n-th from the end of the list, and return the head of the list that is left.
Count from the end: the last node is the first from the end, the node before it is the second, and so on. So
n = 1 deletes the last node, and n equal to the number of nodes deletes the head.
The examples write a list as its values from the head on, so head = [4,1,6] is the list 4 → 1 → 6. The
output shows the list you return the same way. When no nodes are left, return null, which shows as [].
Example 1
Input: head = [6, 2, 9, 4, 7, 1], n = 2
[6,2,9,4,1]Explanation: Counting from the end, the node holding 1 is the first and the node holding 7 is the second. Deleting the node holding 7 links 4 straight to 1.
Example 2
Input: head = [8, 5, 3], n = 3
[5,3]Explanation: The list has three nodes, so the third from the end is the head. After the deletion the list starts at the node holding 5.
Example 3
Input: head = [-4], n = 1
[]Explanation: The only node is also the last one. Deleting it leaves no nodes, so the answer is null.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ number of nodes ≤ 105-109 ≤ Node.val ≤ 1091 ≤ n ≤ number of nodes
Clarifying questions
What you would ask an interviewer before writing any code.